匈牙利算法。
1 #include <stdio.h> 2 #include <string.h> 3 4 #define MAXNUM 1005 5 6 char map[MAXNUM][MAXNUM]; 7 char visit[MAXNUM]; 8 int son[MAXNUM]; 9 10 int find(int x, int m) { 11 int i; 12 13 for (i=0; i<m; ++i) { 14 if (!visit[i] && map[x][i]) { 15 visit[i] = 1; 16 if (!son[i] || find(son[i], m)) { 17 son[i] = x; 18 return 1; 19 } 20 } 21 } 22 23 return 0; 24 } 25 26 int main() { 27 int n, m, k; 28 int i, j; 29 30 while (scanf("%d", &n)!=EOF && n) { 31 scanf("%d %d", &m, &k); 32 memset(map, 0, sizeof(map)); 33 while (k--) { 34 scanf("%*d %d %d", &i, &j); 35 if (i && j) 36 map[i][j] = 1; 37 } 38 k = 0; 39 memset(son, 0, sizeof(son)); 40 for (i=0; i<n; ++i) { 41 memset(visit, 0, sizeof(visit)); 42 if (find(i, m)) 43 ++k; 44 } 45 printf("%d\n", k); 46 } 47 48 return 0; 49 }
【HDOJ】1150 Machine Schedule,布布扣,bubuko.com
原文:http://www.cnblogs.com/bombe1013/p/3761088.html