uva11248专题

UVa11248 - Frequency Hopping

题意:给定一个有向网络,每条边均有一个容量。问是否存在一个从点1到点N,流量为C的流。如果不存在,是否可以恰好修改一条弧的容量,使得存在这样的流?         思路:白书训练指南第一道网络流例题。。先求一次最大流,如果流量至少为C,输出possible,否则需要修改的弧一定是最小割里的弧。依次把这些弧的容量增加到C,然后求最大流,看最大流是否至少为C。不过这样做会超时,需要两