首页 > 代码库 > 【HDOJ】1150 Machine Schedule
【HDOJ】1150 Machine Schedule
匈牙利算法。
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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。