526互联

P2598 [ZJOI2009] 狼和羊的故事

发布时间 2023-09-23 17:45:40作者: OIerBoy

2023-09-22

题目

P2598 [ZJOI2009] 狼和羊的故事

难度&重要性(1~10):6

题目来源

luogu

题目算法

网络流，最小割

解题思路

一道大水题。
考虑如何建图：

  • \(u=1\) 时，\(S\to u\) 流量为 \(inf\)
  • \(u=2\) 时，\(u\to T\) 流量为 \(inf\)
  • 当前点向四周连边，流量为 \(1\)

然后求一个最小割就做完了。

完成状态

已完成