标签为 [网络流] 的文章

BZOJ1797 mincut最小割

题目大意 给定一张网络,询问其中的每条有向边是否可能属于某一个最小割,是否一定属于所有最小割。 Solution 题目是最小割,肯定先跑一次网络流模板…… 求出最小割后,就可以得到一个残余网络。如果对这个残余网络进行强联通缩点,可以发现s,t一定不在同一个强联通分量中。否则,s,t之间肯定还能继续增流,求出的肯定不是最大流。 如果原图中一条边是u->v的,且任意一点u缩点后属于belong[u]的强联通分量中。 如果这条边没有满流,显然它不可能属于某一个最小割。 如果belong[u]!=belong[v],则边u->v可以属于某一个最小割。 ......

POJ2987 Firing

题目大意 你要对一些员工进行裁员,裁掉一个员工都可以获得一些收益(可能为负)。员工之间有上下级关系,要裁掉一个员工,必须要裁掉他的所有下属。问获得的最大收益是多少。 Solution 对于这种最大收益的题,我们可以考虑构造最小割模型。假设我们已经裁掉了那些收益为正的人,但不能裁了上司而不裁下属。设置超级源,将它与所以收益为正的点连边,流量为w[i],表示裁掉了这个人,并将初始答案加上w[i],若割掉这条边,就表示不拿这个人的收益了。再将所有收益为负的点向一个超级汇连边,表示不裁这个人,流量为-w[i],若割掉这 ......