萌新不识二分图
  • 板块学术版
  • 楼主ducati
  • 当前回复4
  • 已保存回复4
  • 发布时间2021/12/11 10:33
  • 上次更新2023/11/3 22:31:28
查看原帖
萌新不识二分图
87064
ducati楼主2021/12/11 10:33

给定一个二分图(左侧有 nn 个点,右侧有 mm 个点),需要找到一组最大独立集,同时在此基础上还要让左侧节点的数量最小

网上说,i[1,n]\forall i \in [1,n] 连边 (S,iL,100)(S,i_L,100)(就是从 11iLi_L 连一条权值为 100100 的便),j[1,m]\forall j \in [1,m] 连边 (jR,T,99)(j_R,T,99),并且所有原来存在的边 (iL,jR)(i_L,j_R) 全部将其流量赋值为 inf\inf,于是跑最大流得到一组最大匹配然后再未匹配点出发寻找增广路就能构造出一组左侧节点的数量最少的最大独立集了。

但是,我并不知道它为何正确;同时,在这样的流量不全是 11 的图上,我不太清楚什么叫做 \lceil 未匹配点 \rfloor\lceil 匹配边 \rfloor

感谢赐教!wtcl.

2021/12/11 10:33
加载中...