BZOJ1797 mincut最小割

题目大意

给定一张网络,询问其中的每条有向边是否可能属于某一个最小割,是否一定属于所有最小割。

Solution

题目是最小割,肯定先跑一次网络流模板……

求出最小割后,就可以得到一个残余网络。如果对这个残余网络进行强联通缩点,可以发现s,t一定不在同一个强联通分量中。否则,s,t之间肯定还能继续增流,求出的肯定不是最大流。

如果原图中一条边是u->v的,且任意一点u缩点后属于belong[u]的强联通分量中。

如果这条边没有满流,显然它不可能属于某一个最小割。

如果belong[u]!=belong[v],则边u->v可以属于某一个最小割。因为这条边已经满流,且割断这条边后,st不连通,所以属于原图的某个最小割。

如果belong[u]=belong[s]且belong[v]=belong[t],则边u->v一定属于原图的所有最小割。因为当这条边的流量增大后,s->t一定可以继续增流,最小割也会变大。所以这条边一定属于最小割。

Code

 

1 条评论
  1. I would like to get across my love for your generosity supporting those people who actually need guidance on this one content. Your real commitment to passing the message up and down was rather significant and has all the time allowed girls much like me to realize their pursuits. Your personal important advice signifies a whole lot a person like me and especially to my colleagues. Warm regards; from everyone of us.

发表一条评论