给定一个二分图(左侧有 n 个点,右侧有 m 个点),需要找到一组最大独立集,同时在此基础上还要让左侧节点的数量最小。
网上说,∀i∈[1,n] 连边 (S,iL,100)(就是从 1 到 iL 连一条权值为 100 的便),∀j∈[1,m] 连边 (jR,T,99),并且所有原来存在的边 (iL,jR) 全部将其流量赋值为 inf,于是跑最大流得到一组最大匹配然后再未匹配点出发寻找增广路就能构造出一组左侧节点的数量最少的最大独立集了。
但是,我并不知道它为何正确;同时,在这样的流量不全是 1 的图上,我不太清楚什么叫做 ⌈ 未匹配点 ⌋ 和 ⌈ 匹配边 ⌋。
感谢赐教!wtcl.