【BZOJ2561】最小生成树

本来觉得无向图做最小割是不是不太对。。

但是想了想没毛病呀 一条边肯定不会被割两次 如果\(u->v\)的边要被割掉说明要把\(u\)出去的路堵死。。那么\(v\)就算能走到\(u\)也走不出去

于是很简单了

一条边要进入最小生成树,那么考虑Kruskal的过程,一定是比它小的边都加完了这两个点还没连通。

所以把比它小的边都加进图,新边的两个点分别作源汇跑最小割。

最大同理。答案相加即可。

说点什么

您将是第一位评论人!

提醒
wpDiscuz