ural 1109 二分图匈牙利算法

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<vector> using namespace std; const int maxn=1005; int n,m,ans,pre[maxn],flag[maxn]; vector<int> edge[maxn]; int dfs(int i) { for(vector<int>::iterator it=edge[i].begin();it!=edge[i].end();it++) { if(!flag[*it]) { flag[*it]=1; if(pre[*it]==0||dfs(pre[*it])) { flag[*it]=1; pre[*it]=i; return 1; } } } return 0; } void solve() { for(int i=1;i<=n;i++) { memset(flag,0,sizeof(flag)); ans+=dfs(i); } printf("%d\n",n+m-ans); } int main() { int x,y,k; scanf("%d%d%d",&n,&m,&k); while(k--&&scanf("%d%d",&x,&y)!=EOF) edge[x].push_back(y); solve(); return 0; }