二分图

Darkness_ · 2018-03-07 13:24:30 · 题解

二分图的概念

二分图又称作二部图，是图论中的一种特殊模型。设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。（源自百度-二分图）

如上图就是一个标准的二分图。

最大匹配与增广路的概念

给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。(源自百度-二分图匹配)

最大匹配即是选择其中边数最大的子集的图。

完全匹配，也叫做完备匹配，即某个匹配中，每个顶点都和某条边相关联。

好的，现在介绍完一个基本概念，我们就要着手解决如何求解最大匹配的问题了。

若要找出二分图中的最大匹配，最朴素的方法就是找出所有的匹配并一一比较，但这种方法的时间复杂度是边数的指数级的，不能满足数据范围较大的问题。因此，我们需要找出一个更优的方法求解。

在寻找这更优的方法前，我们需要先了解增广路的概念：增广路，也称增广轨或交错轨。若P是图G中一条连通两个未匹配顶点的路径，并且属于M的边和不属于M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广路径(举例来说，有A、B集合，增广路由A中一个点通向B中一个点，再由B中这个点通向A中一个点……交替进行)。（源自百度-增广路）

由增广路的定义我们可以推出下述三个结论：

P的路径长度必定为奇数，第一条边和最后一条边都不属于M。
经过取反操作可以得到一个更大的匹配M’，边数为M的边数+1。
M为G的最大匹配当且仅当不存在相对于M的增广路径。

如图为一个二分图增广路集合。

匈牙利算法

匈牙利算法就是用增广路求最大匹配问题(由匈牙利数学家Edmonds于1965年提出)

算法的主要步骤为：

将M设置为空；
找出一条增广路径P，通过取反操作获得更大的匹配M’代替M；
重复2操作直到找不出增广路径为止；

如上图，A-a,a-B,B-b,b-D是一个增广路集合。

那么如果在执行2操作时发现有冲突了怎么办？算法所采取的是一种称作“协商”的手段。关于“协商”这一部分的详解可以查看匈牙利算法

下面给出匈牙利算法(洛谷P3386)的代码

/****************
Keep your dreams.
     by Darkness_
****************/

#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAXN 1005
#define INF 0X3F3F3F3F
#define MOD 1000000007
#define QWQ puts("QWQ")

int read(int &x) {
    x=0;
    int f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9') {
        if (ch=='-')
            f=-f;
        if (ch==EOF)
            return -1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9') {
        x=x*10+ch-48;
        ch=getchar();
    }
    x*=f;
    return 0;
}

int n,m,e,x,y,ans;
int con_x[MAXN],con_y[MAXN];
bool vis[MAXN],flag[MAXN][MAXN];

bool dfs(int x) {
    for (int y=1;y<=m;y++)
        if (flag[x][y]&&!vis[y]) {
            vis[y]=true;
            if (con_y[y]==-1||dfs(con_y[y])) {
                con_x[x]=y;
                con_y[y]=x;
                return true;
            }
        }
    return false;
}

void Maxmatch() {
    memset(con_x,-1,sizeof(con_x));
    memset(con_y,-1,sizeof(con_y));
    for (int i=1;i<=n;i++)
        //if (con_x[i]==-1)//此句应去除，不知道为什么会错（逃
        {
            memset(vis,false,sizeof(vis));
            ans+=dfs(i);
        }
}

int main() {
    read(n);
    read(m);
    read(e);
    for (int i=1;i<=e;i++) {
        read(x);
        read(y);
        if (x>=1&&y>=1&&x<=n&&y<=m)
            flag[x][y]=true;
    }
    Maxmatch();
    printf("%d\n",ans);
    return 0;
}

二分图中的其他性质

关于二分图中其他的性质有：

二分图的最小顶点覆盖最小顶点覆盖要求用最少的点(U或V中都行)，让每条边都至少和其中一个点关联。 Knoig定理：二分图的最小顶点覆盖数等于二分图的最大匹配数。
DAG图的最小路径覆盖用尽量少的不相交简单路径覆盖有向无环图(DAG)G的所有顶点。引理：DAG图的最小路径覆盖数=节点数(n)-最大匹配数(m)
二分图的最大独立集在Ｎ个点的图G中选出m个点，使这m个点两两之间没有边．求m最大值。引理：二分图的最大独立集数 = 节点数(n)—最大匹配数(m)

关于二分图匈利亚算法的介绍就到这里告一段落了，但其实更重要的是建立模型，而这就需要多做题目来找到感觉了。

祝大家Rp++！

在HDU上做一道二分图的题目时here，出现了莫名奇妙的错误，在经过对拍之后，发现此模板对于某一些奇怪的数据存在一定的差错，Maxmatch函数中的一句语句应去除，具体已在代码中注释（顺便改了一下代码格式hhhh）。

P.S.:我把两种写法的二分图对拍了一下，发现没有什么错误。不知道是为什么……痛苦万分

不过以后还是去掉吧……也许就有什么毒瘤数据呢了……