P3386 【模板】二分图匹配(匈牙利算法,增广路,二分图)
题目描述
给定一个二分图,结点个数分别为n,m,边数为e,求二分图最大匹配数
输入输出格式
输入格式:
第一行,n,m,e
第二至e+1行,每行两个正整数u,v,表示u,v有一条连边
输出格式:
共一行,二分图最大匹配。
借鉴: Darkness_大佬的题解:
二分图的概念
二分图又称作二部图,是图论中的一种特殊模型。设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操作时发现有冲突了怎么办?算法所采取的是一种称作“协商”的手段。关于“协商”这一部分的详解可以查看匈牙利算法
#include<bits/stdc++.h>
#define INF 0x3fffffff
#define ll long long
#define mem(ar,num) memset(ar,num,sizeof(ar))
#define me(ar) memset(ar,0,sizeof(ar))
#define lowbit(x) (x&(-x))
#define IOS ios::sync_with_stdio(false)
#define DEBUG cout<<endl<<"DEBUG"<<endl;
#define N 2010
using namespace std;
int n,m,e,ans;
int vis[N][N];
int ask[N],matched[N];
bool found(int x){ //dfs找增广路
for (int i = 1 ; i <= m ; i++)
if (vis[x][i]){
if (ask[i])
continue;
ask[i] = 1;
if (!matched[i] || found(matched[i])) {
matched[i] = x;
return true;
}
}
return false;
}
void match(){
int cnt = 0;//cnt是计数器
memset(matched,0,sizeof(matched));
for (int i = 1 ; i <= n ; i++){
memset(ask,0,sizeof(ask));
if (found(i))
cnt++; //找到了就加1
}
ans = cnt;
}
int main(){IOS;
cin>>n>>m>>e;//结点个数分别为n,m,边数为e
for (int i = 1 ; i <= e ; i++){
int x,y;
cin>>x>>y;
vis[x][y] = 1;
}
match();//匈牙利算法,见上
cout<<ans;
return 0;
}