BZOJ 1001 [BeiJing2006] 狼抓兔子

发布于 2017-05-24  179 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1001

题意:一个 n*m 的网格图,有斜边,边均有边权,切断边权和最小的边集使得无法从 (1,1) 到 (n,m)....


一眼最小割... 然而数据范围应该是过不去的... 敲了一发 dinic 试一试.. 然后就过了... 不知道是数据太水还是 dinic 的上界太松辣....

样例不过... 苦恼了一会发现是无项图... 所以连边直接双向都连边权即可...

正解太神,不会,先放着 orz

 


一个非常弱的准退役OIER