首页 > 代码库 > BestCoder25 1001.Harry and Magical Computer（hdu 5154） 解题报告
BestCoder25 1001.Harry and Magical Computer（hdu 5154） 解题报告
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5154
题目意思：有 n 门 processes（编号依次为1，2，...，n），然后给出 m 种关系： a，b。表示 process b 要在 process a 之前完成。问经过 m 种关系之后，有没有可能完成所有的 process。
可以利用拓扑排序的思想做。遍历所有 process，处理所有入度为 0 的点，然后把与该点关联的点，即度数都减一。这样处理完之后，每个点的度数应该都是-1，否则就代表有环，不能完成所有的process。
1 /* 2 #include <iostream> 3 #include <cstring> 4 #include <cstdio> 5 using namespace std; 6 7 const int maxn = 100 + 10; 8 int set[maxn]; 9 10 int find(int x) 11 { 12 while (x != set[x]) 13 x = set[x]; 14 return x; 15 } 16 17 void merge(int x, int y) 18 { 19 int fx = find(x); 20 int fy = find(y); 21 printf("fx = %d, fy = %d\n", fx, fy); 22 if (fx != fy) 23 { 24 set[fx] = fy; 25 printf("set[%d] = %d\n", fx, fy); 26 } 27 } 28 29 int main() 30 { 31 #ifndef ONLINE_JUDGE 32 freopen("in.txt", "r", stdin); 33 #endif // ONLINE_JUDGE 34 35 int n, m, from, to; 36 while (scanf("%d%d", &n, &m) != EOF) 37 { 38 memset(set, 0, sizeof(set)); 39 for (int i = 1; i <= n; i++) 40 set[i] = i; 41 for (int i = 0; i < m; i++) 42 { 43 scanf("%d%d", &from, &to); 44 merge(to, from); 45 } 46 47 for (int i = 1; i <= n; i++) 48 { 49 printf("set[%d] = %d\n", i, set[i]); 50 51 } 52 53 puts(""); 54 } 55 return 0; 56 } 57 58 */ 59 60 #include <iostream> 61 #include <cstring> 62 #include <cstdio> 63 using namespace std; 64 65 const int maxn = 100 + 10; 66 int map[maxn][maxn]; 67 int in[maxn]; 68 int n, m; 69 70 int main() 71 { 72 #ifndef ONLINE_JUDGE 73 freopen("in.txt", "r", stdin); 74 #endif // ONLINE_JUDGE 75 int from, to; 76 while (scanf("%d%d", &n, &m) != EOF) { 77 memset(map, 0, sizeof(map)); 78 memset(in, 0, sizeof(in)); 79 for (int i = 0; i < m; i++) { 80 scanf("%d%d", &to, &from); 81 if (!map[from][to]) { 82 map[from][to] = 1; 83 in[to]++; // 入度 84 } 85 } 86 for (int i = 1; i <= n; i++) { 87 for (int j = 1; j <= n; j++) { 88 if (!in[j]) { 89 in[j] = -1; 90 for (int k = 1; k <= n; k++) { 91 if (map[j][k]) { 92 map[j][k] = 0; 93 in[k]--; 94 } 95 } 96 break; 97 } 98 } 99 }100 101 bool flag = true;102 for (int i = 1; i <= n; i++) {103 if (in[i] != -1) {104 flag = false;105 break;106 }107 }108 printf("%s\n", flag ? "YES" : "NO");109 }110 return 0;111 }
BestCoder25 1001.Harry and Magical Computer（hdu 5154） 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。