bzoj 1066 [SCOI2007]蜥蜴

Posted by

题目链接

http://www.lydsy.com/JudgeOnline/problem.php?id=1066

题解

每个柱子分成两个结点\(x_i,y_i\),它们之间连边,容量为柱子的高度;
源点向所有有蜥蜴的柱子的\(x_i\)结点连边,容量为1;
所有能跳出去的柱子的\(y_i\)结点向汇点连边,容量为\(INF\);
如果一个柱子能跳到另一个柱子,两个柱子之间的\(x_i\)和\(y_i\)结点互相连边,容量为\(INF\)。
跑一边最大流,求得的是能跑掉的蜥蜴数,用蜥蜴总数减掉它即可。

代码

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注