题目描述
给定一个二分图,结点个数分别为n,m,边数为e,求二分图最大匹配数
输入输出格式
输入格式
第一行,n,m,e
第二至e+1行,每行两个正整数u,v,表示u,v有一条连边
输出格式
共一行,二分图最大匹配
输入输出样例
输入样例#1
1 1 1
1 1
输出样例#1
1
说明
n,m≤1000, 1 ≤u≤n,1≤u≤n, 1≤v≤m,1≤v≤m
因为数据有坑,可能会遇到 v>mv>m 的情况。请把 v>mv>m 的数据自觉过滤掉。
算法:二分图匹配
思路
匈牙利算法模板
C++代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int maxn=1e3+10;
int n,m,e,ans;
int map[maxn][maxn];
int link[maxn<<1],vis[maxn<<1];
inline int read(){
int Forca=0,Barca=1;
char c=getchar();
while(c<'0' || c>'9'){
if(c=='-')
Barca=-1;
c=getchar();
}
while(c<='9' && c>='0'){
Forca=Forca*10+(int)(c-'0');
c=getchar();
}
return Forca*Barca;
}
inline bool dfs(int t){
for(int i=1;i<=m;i++){
if(!vis[i] && map[i][t]){
vis[i]=1;
if(link[i]==-1 || dfs(link[i])){
link[i]=t;
return 1;
}
}
}
return 0;
}
inline int max_match(){
int cnt=0;
memset(link,-1,sizeof(link));
for(int i=1;i<=n;i++){
memset(vis,0,sizeof(vis));
if(dfs(i)) cnt++;
}
return cnt;
}
int main(){
n=read(),m=read(),e=read();
for(int i=1;i<=e;i++){
int x,y;
x=read(),y=read();
if(x>n || y>m) continue;
map[x][y]=1;
}
ans=max_match();
cout<<ans<<endl;
return 0;
}