[PA 2018] Heros

Luogu
IDLGP9079
Time2000ms
Memory256MB
Difficulty
2018PA(波兰)
**题目译自 [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$ 个点以及与其关联的边,使得图中的最长链最短。 ## Input 第一行三个整数,分别表示 $n$ , $m$ , $k$。 接下来 $m$ 行,每行两个整数 $x$ , $y$ ,表示从 $x$ 点到 $y$ 点有一条有向边。 ## Output 一行一个整数,表示图中最长链的长度最小值。 [samples] ## Note #### 样例 1 解释 删除编号为 $4$ 的点后,图中的最长链长度为 $2$ 。即为我们可以得到的最长链长度的最小值。可以验证所有方案中图中最长链长度最小为 $2$ 。 ![](https://cdn.luogu.com.cn/upload/image_hosting/6sgk5qmj.png) ------------ #### 数据范围 **本题采用捆绑测试** 对于 $100\%$ 的数据: - $1 \le n \le 300$ - $0 \le m \le 400$ - $0 \le k \le \min(n,4)$ - $1 \le x < y \le n$
Samples
Input #1
6 5 1
1 3
2 3
3 4
4 5
4 6
Output #1
2
Input #2
3 3 3
1 2
1 3
2 3
Output #2
0
API Response (JSON)
{
  "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$ 个点以及与其关联的边,使得图中的最长链最短。...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments