對酒當歌,人生幾何? 譬如朝露,去日苦多

第一步
开始学习二分图需掌握。
1.增广路径是什么?
其实二分图就是找增广路径,每找到一条增广路径,ans++。所以要弄清增广路径是什么。
2.掌握匈牙利算法。
匈牙利算法就是找增广路径的,所以掌握后就算真正学会二分图。


困惑:
1.无向二分图?有向二分图?
无向二分图:
比如u跟v是增广路,由于每个点都跑了一次,那么u-v和v-u都找了一次,那么无向二分图最后找的是最大匹配点。
有向二分图:
如果有这样三个点,a到b,b到c。那么找的时候肯定会找两次,最后是match[b]=a,match[c]=b。所以相当于找了一条路(a->b->c)上边数。


第二步
二分图最小路径覆盖
目的:找出最少路径数覆盖所有点。(什么样的路径由题目定义)
无向图:单纯的找出最少路径数覆盖所有点的话。
结论:ans=n-二分图最大匹配/2。
想一下无向图最大二分图匹配找出了最多匹配了多少点,那覆盖这些点只需(二分图最大匹配/2)个点,其他点都需要一条边,所以是其他点需要(n-二分图最大匹配)个点,相加得出结果。

有向图:如果一个士兵在u点,他能顺路一直走下去,但不能回走,问需要多少个这样的士兵。
结论:ans=n-二分图最大匹配。
前面已经说过了,有向二分图相当与找到一条路径上的边数,那么找到问题所问的点就很简单了,n-二分图最大匹配。
第三步
二分图最小点覆盖数
目的:选取最少的点,使任意一条边至少有一个端点被选择,图应该形成一个树。
结论:ans=二分图最大匹配。
二分图最大匹配完以后肯定都是由增广路径得来的,那么由增广路径的定义我们可以想到。
~9)@H$}NBL$YM(@$`S32~~J.png

标签: none

添加新评论

  • 上一篇: 感慨
  • 下一篇: 没有了