题目链接：点击打开链接
题目大意：略。
解题思路：二分图最大匹配 + 匈牙利算法。
AC 代码
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a); #define INF 0x3f3f3f3f using namespace std; typedef long long ll; const int maxn=520; int k,un,vn; int vis[maxn], linker[maxn], g[maxn][maxn]; void init() { mem(linker,-1); mem(g,0); } int dfs(int u) { for(int i=1;i<=vn;i++) { if(!vis[i]&&g[u][i]) { vis[i]=1; if(linker[i]==-1 || dfs(linker[i])) { linker[i]=u; return 1; } } } return 0; } int main() { while(~scanf("%d",&k) && k) { scanf("%d%d",&un,&vn); init(); int u,v; while(k--) { scanf("%d%d",&u,&v); g[u][v]=1; } int rs=0; for(int i=1;i<=un;i++) { mem(vis,0); if(dfs(i)) rs++; } printf("%d\n",rs); } return 0; }
