PART 1 什么是二分图
二分图又称作二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。
此图即为一个二分图
PART 2 什么是二分图匹配
给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。
极大匹配(Maximal Matching)是指在当前已完成的匹配下,无法再通过增加未完成匹配的边的方式来增加匹配的边数。最大匹配(maximum matching)是所有极大匹配当中边数最大的一个匹配。选择这样的边数最大的子集称为图的最大匹配问题。
如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。
求二分图最大匹配可以用最大流(Maximal Flow)或者匈牙利算法(Hungarian Algorithm)
PART 3 匈牙利算法
匈牙利算法算法的主要操作就是枚举左边的点，找它第一个与右面点相连的边，然后如果所连点已经与其它点匹配过，则将之前的点与其它与其相连的点匹配，并不断重复此操作，如果之前点不能与其它点匹配则当前枚举的点枚举其下一条边，如果所有边都不行则此点不参与匹配
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#include<vector>
using namespace std;
int g[1100][1100];
int used[1100],wh[1100];
int ans;
int t,n,m;
inline bool work(int now){
int i,j,k;
for(j=1;j<=m;j++)
if(used[j]!=t&&g[now][j]){
used[j]=t;
if(!wh[j]||work(wh[j])){
wh[j]=now;
return 1;
}
}
return 0;
}
inline void go(){
int i,j,k;
for(i=1;i<=n;i++){
t=i;
if(work(i))ans++;
}
}
int main(){
int i,j,k,x,y;
cin>>n>>m>>k;
for(i=1;i<=k;i++){
cin>>x>>y;
if(y<=m)
g[x][y]=1;
}
go();
cout<<ans<<endl;
return 0;
}
附赠最大流做法代码
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#include<vector>
using namespace std;
int g[1100][1100];
int used[1100],wh[1100];
int ans;
int t,n,m;
inline bool work(int now){
int i,j,k;
for(j=1;j<=m;j++)
if(used[j]!=t&&g[now][j]){
used[j]=t;
if(!wh[j]||work(wh[j])){
wh[j]=now;
return 1;
}
}
return 0;
}
inline void go(){
int i,j,k;
for(i=1;i<=n;i++){
t=i;
if(work(i))ans++;
}
}
int main(){
int i,j,k,x,y;
cin>>n>>m>>k;
for(i=1;i<=k;i++){
cin>>x>>y;
if(y<=m)
g[x][y]=1;
}
go();
cout<<ans<<endl;
return 0;
}
附赠最大流做法代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
const int inf=1e9+7;
struct edge{
int c,to,next;
}e[2000000];
int head[5000],level[5000],cnt;
void read(int &x){
int f=1;x=0;
char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+(s-'0');s=getchar();}
x=(f==1?x:-x);
}
void add(int u,int v,int w){
e[cnt].c=w;
e[cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt++;
e[cnt].to=u;
e[cnt].next=head[v];
head[v]=cnt++;
}
int bfs(int s,int t){
queue<int>q;
memset(level,-1,sizeof(level));
q.push(s);
level[s]=0;
while(!q.empty()){
int u,v;
u=q.front();
q.pop();
for(int i=head[u];~i;i=e[i].next){
v=e[i].to;
if(level[v]==-1&&e[i].c){
level[v]=level[u]+1;
q.push(v);
if(v==t)return 1;
}
}
}
if(level[t]==-1)return 0;
return 1;
}
int dfs(int u,int v,int flow){
if(u==v)return flow;
int res=0;
for(int i=head[u];~i;i=e[i].next){
int j=e[i].to;
if(level[j]==level[u]+1&&e[i].c){
int f=dfs(j,v,min(e[i].c,flow-res));
res+=f;
e[i].c-=f;
e[i^1].c+=f;
}
}
if(!res)level[u]=-1;
return res;
}
int main()
{ int n,m,E,i,j,k,u,v,ans=0;
read(n);
read(m);
read(E);
memset(head,-1,sizeof(head));
for(i=1;i<=E;i++){
read(u);
read(v);
if(v>m)continue;
add(u,v+n,1);
}
int s=n+m+1,t=n+m+2;
for(i=1;i<=n;i++){
add(s,i,1);
}
for(i=1;i<=m;i++){
add(n+i,t,1);
}
while(bfs(s,t))
ans+=dfs(s,t,inf);
printf("%d ",ans);
return 0;
}
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
const int inf=1e9+7;
struct edge{
int c,to,next;
}e[2000000];
int head[5000],level[5000],cnt;
void read(int &x){
int f=1;x=0;
char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+(s-'0');s=getchar();}
x=(f==1?x:-x);
}
void add(int u,int v,int w){
e[cnt].c=w;
e[cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt++;
e[cnt].to=u;
e[cnt].next=head[v];
head[v]=cnt++;
}
int bfs(int s,int t){
queue<int>q;
memset(level,-1,sizeof(level));
q.push(s);
level[s]=0;
while(!q.empty()){
int u,v;
u=q.front();
q.pop();
for(int i=head[u];~i;i=e[i].next){
v=e[i].to;
if(level[v]==-1&&e[i].c){
level[v]=level[u]+1;
q.push(v);
if(v==t)return 1;
}
}
}
if(level[t]==-1)return 0;
return 1;
}
int dfs(int u,int v,int flow){
if(u==v)return flow;
int res=0;
for(int i=head[u];~i;i=e[i].next){
int j=e[i].to;
if(level[j]==level[u]+1&&e[i].c){
int f=dfs(j,v,min(e[i].c,flow-res));
res+=f;
e[i].c-=f;
e[i^1].c+=f;
}
}
if(!res)level[u]=-1;
return res;
}
int main()
{ int n,m,E,i,j,k,u,v,ans=0;
read(n);
read(m);
read(E);
memset(head,-1,sizeof(head));
for(i=1;i<=E;i++){
read(u);
read(v);
if(v>m)continue;
add(u,v+n,1);
}
int s=n+m+1,t=n+m+2;
for(i=1;i<=n;i++){
add(s,i,1);
}
for(i=1;i<=m;i++){
add(n+i,t,1);
}
while(bfs(s,t))
ans+=dfs(s,t,inf);
printf("%d ",ans);
return 0;
}