二分图入门

然后今天来学二分图，首先我们来看看二分图的定义。

二分图的定义

首先二分图它是一个图(G)，由点集(V)和边集(E)构成的集合，即G=(V,E)。

除此之外它还满足一个特点，若这个图的点集存在一个划分{V1,V2}使得，任意的e(i,j,w)∈E满足关系，i∈V1,j∈V2或者是i∈V2,j∈V1。那么这个图就被称为一个二分图。

以上是比较数学的说法，而且是自己DIY的(狗头。那说人话就是说，如果你能找到一个合理的方式把点划成两个部分，使得每条边的两个顶点均不同时属于一个部分。那么它就是一个二分图。反之，如果不存在这样的划分满足以上结果，那么它就不是一个二分图。

二分图的一个等价定义是：不含有含奇数条边的环的图。

如果说了这么多让你感觉到还是有一点点难以理解的话，那么我们换一个思路：假设把人比作点，把相爱关系比作边。假设这个人群内没有舔狗(恋情非单向)和男酮，那么它们的关系组成的图就会是一个二分图。时间管理大师(一人同时与多人)不影响它还是一个二分图的，只要没有同就行。不知道这个例子是否够抽象，更易于理解。

举个例子，如下图，它是不是一个二分图？

判断二分图可以用它的性质，显而易见的性质是什么：边连接的两个点一定属于不同集合。用刚刚那个例子再去讲的话就是：没有同的情况下，喜欢男孩的一定都是女孩，而这里我们划分就是以男孩女孩作为依据划分的，接着往下推又可以得到：喜欢喜欢男孩的人的人一定也是男孩。这里我们从1开始，假设1为男，那么5，7必为女，2，8，3必为男，6，4必为女。

我们就可以得到划分：{{1,2,3,8},{4,5,6,7}}。那么我们稍微画的明显一点，将两个划分独立为两排，得到了以下图。

为了方便，我们一般都会把二分图化成这种形式，可以很清楚的发现，同一排之间的点没有连线。那么你现在一定对二分图有了一个较为清楚的认识，那么可能会疑惑，这样的数据结构能用来处理什么样的问题呢？那么就涉及到我们接下来讲的概念了。

一些概念

匹配(matching)：匹配其实就是一个边的集合，任意两条属于匹配的边都没有公共顶点，那么这个集合就叫做这个图的一个匹配。
匹配点：如果这个点存在于这个匹配的任意一条边上，那么这个点就是一个匹配点。
匹配边：如果这个边属于这个匹配，那么这就是一个匹配边。
非匹配点：与匹配点相对
非匹配边：与匹配边相对
最大匹配：在所有匹配中，所含边数量最多的称为最大匹配。
完美匹配：如果一个匹配中的所有边包含了一个图的所有点，即，一个图当中所有的点都为匹配点时，这个匹配称为完美匹配，并非所有的图都含有完美匹配，完美匹配一定是最大匹配。

实际应用

比如还是上面这个图，假设它们就是四男四女，我们要怎样做，才能尽可能保证它们都和自己喜欢的人凑成一对呢？这实际上就是要求二分图的最大匹配了，最大匹配我们一般是用匈牙利算法，对于匈牙利算法，我们需要再补充一点概念。

交替路：如果从一个非匹配点出发，依次经过匹配边，非匹配边，匹配边，非匹配边……形成的路径就叫交替路。
增广路：如果交替路的终点为一个非匹配点，那么这条交替路我们又叫增广路。

如下图

红色点和红色边为匹配点和匹配边，这是一条增广路。

增广路的性质就是非匹配边会比匹配边多一条。如果我们把匹配边和非匹配边交换顺序，那么将会得到

可以到相比之前多了一个匹配边和两个匹配点。但是匹配顺序完全不一样了，原来是2，3匹配，4，5匹配，现在2，3和4，5都不在同一条匹配边上。

匈牙利算法的本质就是不停寻找增广路，增加匹配数目的。我们先不考虑匈牙利算法的代码，先徒手做一遍。首先我们需要匹配的点只有一边，另一边是被匹配的。

如最开始那个图，

从1开始，遍历边，先看1，5，发现5未被匹配，则直接匹配，结束。

那么现在的图是这样的。

从2开始，2未被匹配，则寻找与它相连的边，找到(2,5)，但是发现5已经被匹配了，这个时候就要用到寻找增广路的思维了。那么我们直接沿着匹配边搜寻，就找到了1，然后从1开始找相连的边，因为不能反复横跳，所以我们只能选择7，发现7没被匹配，因此2-5-1-7构成增广路，找到增广路之后代表首位两个点参与进了匹配。然后交换匹配边与非匹配边。成了这样

这里我们不考虑最好的情况，因为我们自己很清楚3，6匹配，4，8匹配直接就完结撒花了。但是计算机不一定按照这样的方式去遍历，你要保证先后顺序不影响最终结果，即就算你选择5，最终算出来的最大匹配应当也是4。

这里我们选5，发现5被匹配了，于是找到2，但是2之后再也找不到路径了，因此(3,5)方向上的增广路寻找失败，所以就会找(3,6)，(3,6)直接匹配，我们看看最后这个8会怎么样呢，我们假设也是先找到了7，7会找到1，1会找到5，5找到2，发现2找不到增广路了，返回失败。所以最终选择了(8,4)。那么这样一整个就是匈牙利算法了。

这里用C代码大概写一下，假设存图采用链式前向星。

#include<bits/stdc++.h>
using namespace std;
struct eee{
    int to;
    int next;
}edge[MAX_EDGE];
int match[MAX_NODE],check[MAX_NODE],root[MAX_NODE];
vector<int>s;//存储一边的点集
void add(int x,int y){
    edge[++cnt].to=y;
    edge[cnt].next=root[x];
    root[x]=cnt;
}
int dfs(int u){
    for(int i=root[u];i;i=edge[i].next){
        int v=edge[i].to;
        if(!check[v]){
            check[v]=true;
            if(match[v]==-1||dfs(match[v])){
                match[u]=v;
                match[v]=u;
                check[v]=false; 
                return true; 
            }
        }
    }
    return false;
}
int xyl(){
    int ans=0;
    for(int i=0;i<s.size();i++){
        if(match[s[i]]==-1){
            check[s[i]]=true;
            if(dfs(s[i]))ans++;
            
        }

    }
    return ans;
}

例题

洛谷P1129

小 Q 是一个非常聪明的孩子，除了国际象棋，他还很喜欢玩一个电脑益智游戏――矩阵游戏。矩阵游戏在一个 n nn×n 黑白方阵进行（如同国际象棋一般，只是颜色是随意的）。每次可以对该矩阵进行两种操作：

行交换操作：选择矩阵的任意两行，交换这两行（即交换对应格子的颜色）。
列交换操作：选择矩阵的任意两列，交换这两列（即交换对应格子的颜色）。

游戏的目标，即通过若干次操作，使得方阵的主对角线(左上角到右下角的连线)上的格子均为黑色。

对于某些关卡，小 Q 百思不得其解，以致他开始怀疑这些关卡是不是根本就是无解的！于是小 Q 决定写一个程序来判断这些关卡是否有解。

题意简单明了就是给一个01矩阵，问你能不能通过行交换与列交换将主对角线的元素都变成1。

那么其实就是每一行找到一个1，使得每个1处于不同的列。只要找到，那么经过若干次交换一定能使主对角线元素都为1。如果第一行的第三列存在一个1，那么就让1和3相连。当然因为这里的3不能和第三行混淆，所以我们选择列数+n作为二分图的另一个点集。所以我们只需要让行列都匹配那就完成了。

#include<bits/stdc++.h>
using namespace std;
struct eee{
    int to;
    int next;
}edge[100000];
int cnt,n,root[501],check[500],match[500];
void add(int x,int y){
    //printf("%d %d\n",x,y);
    edge[++cnt].to=y;
    edge[cnt].next=root[x];
    root[x]=cnt;
}
int dfs(int u){
    for(int i=root[u];i;i=edge[i].next){
        int v=edge[i].to;
        if(!check[v]){
            check[v]=true;
            if(match[v]==-1||dfs(match[v])){
                match[u]=v;
                match[v]=u;
                check[v]=false; 
                return true; 
            }
        }
    }
    return false;
}
int xyl(){
    int ans=0;
    for(int i=1;i<=n;i++){
        if(match[i]==-1){
            check[i]=true;
            if(dfs(i))ans++;
            
        }

    }
    return ans;
}
void solve(){
    cin>>n;
    memset(root,0,sizeof(root));
    for(int i=1;i<=2*n;i++)match[i]=-1;
    cnt=0;
    string s;
    getchar();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int x;
            cin>>x;
            if(x==1){
                add(i,j+n);
                add(j+n,i);
            }
        }
    }
    if(xyl()==n){
        printf("Yes\n");
    }
    else{
        printf("No\n");
    }
}
int main(){
    //freopen("1.in","r",stdin);
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

这里被卡了有点久，最后发现是数组越界，在使用前向星存无向图的时候一定要记得开两倍内存，不然写越界了很难说错误在哪。

血淋淋的教训，并且失败的俩测试点没有报错re，而是wrong answer。