【BZOJ1797】【AHOI2009】最小割

妈的我弃疗了 背结论算了

将残量网络Tarjan缩点,那么

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

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

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

说点什么

1 评论 在 "【BZOJ1797】【AHOI2009】最小割"

提醒
排序:   最新 | 最旧 | 得票最多
游客

泥又在刷火题

wpDiscuz