SHENXN's BLOG

Purdue University
Computer Science, Math

Xiaonan Shen's avatar Xiaonan Shen

[BZOJ1001][BEIJING2006]狼抓兔子(最小割 + DIJKSTRA)

这道题很裸的最小割,只是数据规模大,目测会T(WJS大爷说在BZ上能过,真是跪烂了),其实最小割可以转成最短路的做法。一种做法是转成对偶图然后求最短路,当然我不会,就只好去墙角画圈圈了。不过有一天没事乱翻LRJ的白书突然就翻到了这道题(我真的只是乱翻),然后就观摩了一下题解。转什么对偶图啊。。对于这道题,由于这个图样子比较特殊,可以知道割线必然是一条从图的左边界或下边界的边出发,经过若干条边到达右边界或上边界的边,需要的狼的数量就是经过的所有边的权值和。     Read more