二分图

· · 算法·理论

一、相关概念与理论：

  1. 二分图 ： 设 G=(V,E) 是一个无向图，如果顶点 V 可分割为两个互不相交的子集 (A,B) ，并且图中的每条边 (i,j) 所关联的两个顶点 i 和 j 分别属于这两个不同的顶点集 (i \in{A},j \in{B}) ，则称图G为一个二分图。

  2. 匹配：对于二分图来讲，每个边不存在公共端点时实现匹配。
    *极大匹配：是指在当前已完成的匹配下,无法再通过增加未完成匹配的边的方式来增加匹配的边数。
    *最大匹配：是所有极大匹配当中边数最大的一个匹配。

  3. 最大匹配数：边数最多的匹配的边数

  4. 匹配点，非匹配点：是否匹配的点

  5. 增广路径：对于二分图，从一边的非匹配点开始，路径按照匹配点，非匹配点，匹配点……的顺序，一直到另一边的非匹配点。

  6. 最小点覆盖：对于任意图来讲，选出数量最少的点集, 使得每一条边至少有一个顶点被选中即实现最小点覆盖。

  7. 最大独立集：对于任意图来讲，选出最多的点，使得任意两点间都没有路径。

  8. 最大团：对于任意图来讲，选出最多的点，使得任意两点间都存在路径。

  9. 最小路径覆盖：对于一个DAG，最少用多少条互不相交的路径（点不重复）将所有点覆盖

  10. 最小路径重复覆盖：对于一个DAG，最少用多少条路径将所有点覆盖。
    为了求最小路径重复覆盖，需要先对原图中传递闭包（见《图论1·四、最短路·floyd专题·例2——传递闭包》），在对新图求最小路径覆盖。

1.\textbf{最大匹配} \Longleftrightarrow \textbf{不存在增广路径} 2.\textbf{在二分图中，最小点覆盖=最大匹配数}

因为求最大独立集，就是去掉最少的点，使得相连的边被破环，就是求最小点覆盖，所以

3.\textbf{在二分图中，最大匹配数 = 最小点覆盖 = 总点数 - 最大独立集}

要求最小路径覆盖，先对原图拆点，将一个点分成两个点，一个为出点，一个为入点，再按照原图边的节点编号从出点向入点连一条无向边，此时新图成为二分图，可以得到，最小路径上的每条边组成了新图的最大匹配，而出点中的非匹配点即为所有最小路径覆盖路径的终点，所以

4.\textbf{在二分图中，最大匹配数 = 最小点覆盖 = 总点数 - 最小路径覆盖}

二、算法大纲：

实质类似 DFS ，时间复杂度 O(n+m)。

时间复杂度 O(n·m) 。但实际运行时间远小于 O(n·m) 。

三、算法内容：

1.染色法：

当且仅当一个图中不含奇数环。

奇数环：边的数量为奇数的环。

为什么呢？

这是因为奇数环本身就不符合二分图的性质，假如我们把图的点染成两种不同颜色，那么在染这个奇数环时，就无法保证相同颜色一定不相邻。 

给定一个n个点m条边的无向图，图中可能存在重边和自环。

请你判断这个图是否是二分图。

输入格式
第一行包含两个整数n和m。

接下来m行，每行包含两个整数u和v，表示点u和点v之间存在一条边。

输出格式
如果给定图是二分图，则输出“Yes”，否则输出“No”。

数据范围
1≤n,m≤10^5

输入样例：
4 4
1 3
1 4
2 3
2 4
输出样例：
Yes

source：Acwing.860

DFS的方式是，以一个点为起始染色点，遍历所有它相连的边，判断是否染色，未染则染并DFS，若染则判断，色相同则不为二分图。

由于题目未提及是否是一个连通图，所以有可能存在多块连通图，所以以每个点为起始染色点都DFS一遍。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n,m;

int col[N];//点的颜色：0是未染色，1、-1是两种不同颜色 

int st[N],fi[N*2],ne[N*2],idx;//前向星 
void add(int a,int b){
    fi[idx]=b,ne[idx]=st[a],st[a]=idx++;
} 

bool dfs(int u,int c){
    col[u]=c;//染色 
    for(int i=st[u];i!=-1;i=ne[i]){
        int j=fi[i];
        if(col[j]==0){//未染则染 
            if(!dfs(j,-c))  return false;
        }else{//若染则判断 
            if(col[j]==c)   return false;
        }
    }

    return true;
}

int main(){
    memset(st,-1,sizeof st);//前向星初始化 
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
        add(b,a);//双相建边 
    }

    bool flag=true;//表示是否有染色冲突 

    for(int i=1;i<=n;i++){
        if(col[i]==0){
            if(dfs(i,1)==false){
                flag=false;
                break;
            }
        }
    }

    if(flag)    printf("Yes");
    else    printf("No");
    return 0;
}

这样的染色法也是有巨大用处的，例如做：P1525 [NOIP2010 提高组] 关押罪犯,加上整体二分即可。

2.匈牙利算法：

给定一个二分图G(X,E,Y)，F为边集E的一个子集。如果F中任意两条边都没有公共端点，则称F是图G的一个匹配。

极大匹配(Maximal Matching)是指在当前已完成的匹配下,无法再通过增加未完成匹配的边的方式来增加匹配的边数。最大匹配(maximum matching)是所有极大匹配当中边数最大的一个匹配。

举一个例子，有一些男生女生，他们互相之间有所认识与好感度，现在来确定最多有多少对对子。此时，“男生女生”就是点，“好感度”就是边。

给定一个二分图，
其中左半部包含 n1 个点（编号 1∼n1），右半部包含 n2 个点（编号 1∼n2），
二分图共包含 m 条边。

数据保证任意一条边的两个端点都不可能在同一部分中。

请你求出二分图的最大匹配数。

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

二分图的最大匹配：所有匹配中包含边数最多的一组匹配被称为二分图的最大匹
配，其边数即为最大匹配数。

输入格式
第一行包含三个整数 n1、 n2 和 m。

接下来 m 行，每行包含两个整数 u 和 v，表示左半部点集中的点 u 和右半部点集中的点 v 之间存在一条边。

输出格式
输出一个整数，表示二分图的最大匹配数。

数据范围
1≤n1,n2≤500,1≤u≤n1,1≤v≤n2,1≤m≤105

输入样例：
2 2 4
1 1
1 2
2 1
2 2
输出样例：
2

source：Acwing.861

如果你想找的妹子已经有了男朋友，你就去问问她男朋友:“你有没有备胎，把这个让给我好吧？”（真是渣）

枚举每一个左部点 u 的每一条边，若终点 v 没有匹配，那么直接将 u 匹配 v。若终点匹配，则让 v 的 “原配”左部点去匹配其他右部点 ，如果“原配”匹配到了其他点，那么将 u 匹配 v；否则 u 失配。

#include<bits/stdc++.h>
using namespace std;
const int N=510,M=100010;
int n[3],m;

bool s[N];//仅存左半部分的模拟预定情况 

int mat[N]; //右半部分的匹配情况 

int st[N],fi[M],ne[M],idx;//仅有左半部分指向右半部分的边 
void add(int a,int b){
    fi[idx]=b,ne[idx]=st[a],st[a]=idx++;
}

bool find(int b){//模拟匹配 
    for(int i=st[b];i!=-1;i=ne[i]){
        int g=fi[i];//找到一个 
        if(!s[g]){//是否已被模拟预定 
            s[g]=true;//模拟预定 
            if(mat[g]==0 || find(mat[g])){
            //若本来没有就匹配；若有就尝试模拟更换， 
                mat[g]=b;
                return true;//匹配成功 
            }
        }//继续尝试 
    }

    return false;//模拟不成立 
}

int main(){
    memset(st,-1,sizeof st);
    memset(mat,0,sizeof mat);

    scanf("%d %d %d ",&n[1],&n[2],&m);

    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d %d",&u,&v);
        add(u,v);
    }

    int num=0; 

    for(int i=1;i<=n[1];i++){//贪心模拟 
        memset(s,false,sizeof s);//模拟初始化 
        if(find(i)) num++;
    }

    printf("%d",num);
    return 0;
}

3.板子训练

题单

四、算法应用

这道题的思路是整体二分答案，加上二分图染色法判断可行性。

注意，虽然不是判断二分图，但是却在判断可行性，那么这其实是在判断最大匹配的极大可行性，所以不要混淆。

在上面的理论中，我们已经得到了方法，即

将原图的每个点拆成两个点，一个点只连其出边，称为入点，一点只连其入边，称为出点，此时形成二分图并经行最小匹配，每一个匹配便是最小路径集合中路径上的一条边，寻找输出。

是不是太抽象了？显然，一个DAG的最小路径匹配不一定只有一种方案，其中二分最大匹配得到的是一种方案，在这个过程中，

  1. 当由一个点分裂得到的入点和出点都得到匹配，这意味着有两条路径首尾相连；
  2. 当找到了增广路径，这意味着出现了两条路径将要交叉，而我们使得另一条路径绕行，或者无法绕行将想加长的路径截止。

那么具体操作还是看样例代码吧。

在上面，我们已经搞定了最小路径覆盖，最小路径重复覆盖与其大同小异，只需要先做一遍传递闭包（见《图论1·四、最短路·floyd专题·例2——传递闭包》），再按最小路径覆盖做就可以了。

其中，在找到增广路径即在遇到交叉点时，仍然不允许想加长的路径加长，然而由于传递闭包，使得想加长路径可以绕开交叉点，与交叉点到的其他点相连，间接覆盖交叉点。

当然，由于上述问题，最小路径重复覆盖的路径输出不能按照最小路径覆盖的方式做。

放个具体代码吧：样例代码2。

-