{"problem":{"name":"[PA 2018] Heros","description":{"content":"**题目译自 [PA 2018](https://sio2.mimuw.edu.pl/c/pa-2018-1/dashboard/) Runda 2 [Heros](https://sio2.mimuw.edu.pl/c/pa-2018-1/p/her/)** 给定一个有向无环图，该图有 $n$ 个节点， $m$ 条有向边。 你需要从中删除 $k$ 个点以及与其关联的边，使得图中的最长链最短。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9079"},"statements":[{"statement_type":"Markdown","content":"**题目译自 [PA 2018](https://sio2.mimuw.edu.pl/c/pa-2018-1/dashboard/) Runda 2 [Heros](https://sio2.mimuw.edu.pl/c/pa-2018-1/p/her/)**\n\n给定一个有向无环图，该图有 $n$ 个节点， $m$ 条有向边。\n\n你需要从中删除 $k$ 个点以及与其关联的边，使得图中的最长链最短。\n\n## Input\n\n第一行三个整数，分别表示 $n$ , $m$ , $k$。\n\n接下来 $m$ 行，每行两个整数 $x$ , $y$ ，表示从 $x$ 点到 $y$ 点有一条有向边。\n\n## Output\n\n一行一个整数，表示图中最长链的长度最小值。\n\n[samples]\n\n## Note\n\n#### 样例 1 解释\n\n删除编号为 $4$ 的点后，图中的最长链长度为 $2$ 。即为我们可以得到的最长链长度的最小值。可以验证所有方案中图中最长链长度最小为 $2$ 。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/6sgk5qmj.png)\n\n------------\n\n#### 数据范围\n\n**本题采用捆绑测试**\n\n对于 $100\\%$ 的数据：\n\n- $1 \\le n \\le 300$\n- $0 \\le m \\le 400$\n- $0 \\le k \\le \\min(n,4)$\n- $1 \\le x < y \\le n$","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9079","tags":["2018","PA（波兰）"],"sample_group":[["6 5 1\n1 3\n2 3\n3 4\n4 5\n4 6","2"],["3 3 3\n1 2\n1 3\n2 3","0"]],"created_at":"2026-03-03 11:09:25"}}