首页 > 代码库 > poj 1094 Sorting It All Out 解题报告

poj 1094 Sorting It All Out 解题报告

2024-07-17 12:33:59   220人阅读

题目链接：http://poj.org/problem?id=1094

题目意思：给出 n 个待排序的字母 和 m 种关系，问需要读到第 几 行可以确定这些字母的排列顺序或者有矛盾的地方，又或者虽然具体的字母顺序不能确定但至少不矛盾。这些关系均是这样的一种形式： 字母1 < 字母2

　　这道题目属于图论上的拓扑排序，由于要知道读入第几行可以确定具体的顺序，所以每次读入都需要进行拓扑排序来检验，这时每个点的入度就需要存储起来，所以就有了代码中memcpy 的使用了。

    拓扑排序的思路很容易理解，但写起来还是需要注意很多细节。参考了别人的代码，第一次写，受益匪浅啊。

   

  1 #include <iostream>  2 #include <cstdio>  3 #include <cstring>  4 #include <vector>  5 #include <queue>  6   7 using namespace std;  8   9 const int maxn = 26 + 5; 10 vector<int> vi[maxn]; 11 queue<int> q; 12 int in[maxn], temp[maxn]; 13 int n, m, cnt; 14 char ans[maxn], input[5]; 15  16 bool check(int x, int y)     // 检查之前是否插入过该边 17 { 18     for (int i = 0; i < vi[x].size(); i++) 19     { 20         if (vi[x][i] == y) 21             return true; 22     } 23     return false; 24 } 25  26 int Toposort() 27 { 28     while (!q.empty()) 29         q.pop(); 30     for (int i = 0; i < n; i++) // 将入度为0的点入队 31     { 32         if (!in[i]) 33             q.push(i); 34     } 35     bool unsure = false; 36     cnt = 0; 37     while (!q.empty())    // 取出第一个入度为0的点 38     { 39         if (q.size() > 1) // 假如有n个点的DAG入度为0的点只有一个，那么就可以确定已排好序 40             unsure = true; 41         int tmp = q.front(); 42  43         ans[cnt++] = tmp + ‘A‘; 44         q.pop(); 45         for (int i = 0; i < vi[tmp].size(); i++) // 该点引出的边删除 46         { 47             in[vi[tmp][i]]--;      // 即入度减1 48             if (!in[vi[tmp][i]])  // 恰好入度减1后，该点入度变为0 49                 q.push(vi[tmp][i]); 50         } 51     } 52     if (cnt < n)   // 有环 53         return 2; 54     if (unsure)    // 有待进一步斟酌 55         return 3; 56     return 1;      // 已经排好序 57 } 58  59 int main() 60 { 61     int step, flag; 62     while (scanf("%d%d", &n, &m) != EOF && (m || n)) 63     { 64         for (int i = 0; i < maxn; i++) 65             vi[i].clear(); 66         bool ok = false; 67         memset(in, 0, sizeof(in)); 68         for (int i = 1; i <= m; i++) 69         { 70             scanf("%s", input); 71             if (ok) 72                 continue; 73             int l = input[0] - ‘A‘; 74             int r = input[2] - ‘A‘; 75             if (!check(l, r)) 76             { 77                 vi[l].push_back(r); 78                 in[r]++; 79             } 80             memcpy(temp, in, sizeof(in));   // 每个点的入度数处理前先拷贝一份以待下一次输入再用 81             flag = Toposort(); 82             memcpy(in, temp, sizeof(temp)); 83             if (flag != 3)   // 暂时不能判断属于哪种情况，先保存step数 84             { 85                 step = i; 86                 ok = true; 87             } 88         } 89         if (flag == 1) 90         { 91             ans[cnt] = ‘\0‘; 92             printf("Sorted sequence determined after %d relations: %s.\n", step, ans);  93         } 94         else if (flag == 2) 95             printf("Inconsistency found after %d relations.\n", step); 96         else 97             printf("Sorted sequence cannot be determined.\n"); 98     } 99     return 0;100 }

 


联系
我们