Chlience

【算法】浅谈二分图
很简单的一点东西,写给自己看的最近做了一波题,发现自己对二分图还是停留在 背诵 的阶段,重读了一遍博客,发现这个东...
扫描右侧二维码阅读全文
01
2019/02

【算法】浅谈二分图

很简单的一点东西,写给自己看的

最近做了一波题,发现自己对二分图还是停留在 背诵 的阶段,重读了一遍博客,发现这个东西还是很有趣的,特此记录

所谓 二分图 ,是指能够被黑白二染色的图,任意一条边都连接着一个黑点和一个白点
至于 匹配 ,则是指在二分图中选出一些边,要求没有公共顶点

我们定义 匹配边 为匹配中的边, 匹配点 为匹配中边的顶点

一个 最大匹配 也就是所有匹配中匹配边最多的一个匹配
那么,寻找 二分图最大匹配 的过程,就是匹配边,匹配点不断增加的过程

如何增加匹配边,匹配点呢?

这就要引入 交替路 了:
从一个未匹配点出发,走非匹配边,匹配边,非匹配边...
如果遇到任何一个非匹配点,显然最后一条边是非匹配边
那么只需要将这条路径上的匹配边/非匹配边互换,即可将首尾两个点变成匹配点
显然,交换后匹配大小 + 1

同样,如果从一个匹配点开始,先手必胜不断寻找交替路的过程即为匈牙利算法,通常使用 DFS 实现

bool dfs(int x) {
    for(int i = head[x] ; i ; i = e[i].n) {
        if(use[e[i].t] != times) {
        //如果走过了这个点,显然上一次就失败了,这一次还找个啥
            use[e[i].t] = times;
            if(!match[e[i].t] || dfs(match[e[i].t])) {
            //是否是匹配点,修改匹配
                match[e[i].t] = x;
                //所谓match即为T集合中每个匹配点必有的匹配边(往回走),如果需要从该点增广,必然要解决掉这条匹配边
                return true;
            }
        }
    }
    return false;
}

在一些博弈问题中,特别是像是一类在棋盘上移动棋子的题目,常常可以对其进行二分图染色,同样有一些奇妙的性质

在这里不过多的进行分析,等到下一篇博客再进行讲解吧

Last modification:February 1st, 2019 at 10:45 am

Leave a Comment