二分图匹配（匈牙利算法）

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> using namespace std; int a[1010][1010]; int match[1010]; int p[1010]; int n,m; int dfs(int u){ int i; for(int i=1;i<=m;i++){ if(p[i]==0&&a[u][i]){ p[i]=1; if(match[i]==0||dfs(match[i])){ match[i]=u; return 1; } } } return 0; } int main(){ int i,j,k,e; scanf("%d%d%d",&n,&m,&e); for(i=1;i<=e;i++){ int x,y; scanf("%d%d",&x,&y); a[x][y]=1; } for(i=1;i<=n;i++)match[i]=0; int sum=0; k=max(n,m); for(i=1;i<=n;i++){ for(j=1;j<=k;j++)p[j]=0; if(dfs(i))sum++; } printf("%d",sum); return 0; }