二分图最大匹配，裸题 本题要点： 1、左部节点：n个点， 右部节点：m个点 n <= 500, 用邻接矩阵存图，还可以有效去掉重边 2、增广路算法，套模板
#include <cstdio> #include <cstring> #include <iostream> using namespace std; const int MaxN = 510; int a[MaxN][MaxN], match[MaxN]; int n, m, e; bool vis[MaxN]; bool dfs(int x) { for(int y = 1; y <= m; ++y) { if(!a[x][y] || vis[y]) continue; vis[y] = true; if(!match[y] || dfs(match[y])) { match[y] = x; return true; } } return false; } int main() { int x, y; while(scanf("%d%d%d", &n, &m, &e) != EOF) { memset(a, 0, sizeof a); memset(match, 0, sizeof match); for(int i = 0; i < e; ++i) { scanf("%d%d", &x, &y); a[x][y] = 1; } int ans = 0; for(int i = 1; i <= n; ++i) { memset(vis, false, sizeof vis); if(dfs(i)) ++ans; } printf("%d\n", ans); } return 0; } /* 1 1 1 1 1 */ /* 1 */ /* 4 2 7 3 1 1 2 3 2 1 1 4 2 4 1 1 1 */ /* 2 */