匈牙利算法模板,有个博客讲得很好:趣写算法系列之--匈牙利算法
#include <iostream> #include <stdlib.h> #include <stdio.h> #include <string.h> #include <math.h> #include <algorithm> using namespace std; const int maxn = 510; int pp[maxn][maxn], map[maxn], vis[maxn]; int k, m, n; bool find_path(int x) { for(int i = 1; i <= n; i++) { if(pp[x][i] && !vis[i]) { vis[i] = 1; if(map[i] < 0 || find_path(map[i])) { map[i] = x; return true; } } } return false; } int main() { //freopen("2063.in", "r", stdin); while(scanf("%d%d%d", &k, &m, &n) && k) { int a, b, ans; memset(pp, 0, sizeof(pp)); memset(map, -1, sizeof(map)); for(int i = 0; i < k; i++) { scanf("%d%d", &a, &b); pp[a][b] = 1; } ans = 0; for(int i = 1; i <= m; i++) { memset(vis, 0, sizeof(vis)); if(find_path(i)) ans++; } printf("%d\n", ans); } return 0; }