求助
  • 板块灌水区
  • 楼主Azurite
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/10/12 17:11
  • 上次更新2024/10/12 20:04:10
查看原帖
求助
403976
Azurite楼主2024/10/12 17:11

网络流求最小割时若要求出最小割边,oiwiki上的解释是把最大流求出来后把未满流的边容量改为1,满流的边容量设为inf后再求一次最小割(即再跑一边Dinic最大流)。但是根据最小割的定义,跑最大流求出的最小割是把容量大于0的边构成的残量网络中s源点能到达的点作为S点集,其他点作为T点集,S到T的边的容量总和。显然每个S到T中与汇点相连的容量大于0的边都必须割去,那么是不是只需要统计与S相连的点与与T相连的点的容量大于0的边数量即可?

2024/10/12 17:11
加载中...