【BZOJ1797】【AHOI2009】最小割

妈的我弃疗了 背结论算了

将残量网络Tarjan缩点,那么

一条边能够在最小割中->这条边的两个端点不在同一个强连通分量中。

一条边一定在最小割中->这条边的\(u\)和\(S\)在同一强连通分量中且\(v\)和\(T\)在同一强连通分量中。

然后就是一条边要出现在最小割中它在最大流时一定被流满了。所以还要先判一下这条边是否有流量,压根没有流量的话也会满足第一个条件。

1
说点什么

1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
游客

泥又在刷火题