HDU 6214 Smallest Minimum Cut 最小割的割边的数目最少

Smallest Minimum Cut

题意

给一个有向的网络图,每条边有一定的容量$w_i$,现在以$1$点为源点,$n$点为汇点。求一组最小割的割边,使边的数目最少,输出最少数目。

建图&思路

直接按照原网络建图,只是边的容量改变为$10000 * w_i +1$,其中边的条数$m<10000$。这样跑最大流(最小割)后,假设最大流为$flow$,那么$flow / 10000$就是原始网络的最大流(最小割),$flow \mod 10000$就是最小割的最少边的条数。

代码

 

发表评论

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