给定一个二分图G，M为G边集的一个子集，如果M满足当中的任意两条边都不依附于同一个顶点，则称M是一个匹配。极大匹配(Maximal Matching)是指在当前已完成的匹配下,无法再通过增加未完成匹配的边的方式来增加匹配的边数。最大匹配(maximum matching)是所有极大匹配当中边数最大的一个匹配。选择这样的边数最大的子集称为图的最大匹配问题。如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。
求二分图最大匹配可以用最大流(Maximal Flow)或者匈牙利算法(Hungarian Algorithm)
这里做的题目是poj3041，把算法都弄懂了之后，发现它真的很水。
#include <iostream>
using namespace std;
int m,n,p,q,s,t,jie=0;
bool g[505][505]={0};
int di[505];
bool y[505];
bool find(int v){
for (int i=1;i<n+1;i++){
if (g[v][i]&&!y[i]){
y[i]=true;
if (di[i]==0||find(di[i])){
di[i]=v;
return true;
}
}
}
return false;
}
int main(){
int i,j;
cin>>n>>m;
for (i=0;i<m;i++){
cin>>s>>t;
g[s][t]=true;
}
for (i=1;i<n+1;i++) {
for (j=1;j<n+1;j++) y[j]=false;
if (find(i)) jie++;
}
cout<<jie<<endl;
return 0;
}
