Loading... # ACWing 343 排序 题解 ## 题目描述 给定$n$个变量和$m$个不等式。其中$n$小于等于$26$，变量分别用前$n$的大写英文字母表示。 不等式之间具有传递性，即若$A>B$且$B>C$，则$A>C$。 请从前往后遍历每对关系，每次遍历时判断： - 如果能够确定全部关系且无矛盾，则结束循环，输出确定的次序； - 如果发生矛盾，则结束循环，输出有矛盾； - 如果循环结束时没有发生上述两种情况，则输出无定解。 #### 输入格式 输入包含多组测试数据。 每组测试数据，第一行包含两个整数$n$和$m$。 接下来$m$行，每行包含一个不等式，不等式全部为小于关系。 当输入一行 `0 0` 时，表示输入终止。 #### 输出格式 每组数据输出一个占一行的结果。 结果可能为下列三种之一： 1. 如果可以确定两两之间的关系，则输出 `"Sorted sequence determined after t relations: yyy...y."`,其中`'t'`指迭代次数，`'yyy...y'`是指升序排列的所有变量。 2. 如果有矛盾，则输出： `"Inconsistency found after t relations."`，其中`'t'`指迭代次数。 3. 如果没有矛盾，且不能确定两两之间的关系，则输出 `"Sorted sequence cannot be determined."`。 ## 解题思路 显然这道题是在集合$x$上的二元关系的一个传递闭包， 由离散数学的知识可得， 二元关系上的传递闭包可以由Floyd算法求出: 设`dist[i][j]`代表`i<j`, 当`dist[i][k]==true`且`dist[k][j]==true`的情况下`dist[i][j]`一定为真 下面讨论如何处理三种输出： - 存在矛盾，提前终止：假设有$B<A$和$C<B$， 当且仅当$A<C$时候存在矛盾。考虑当前的传递闭包， 因为`dist[A][C]== true`且`dist[C][A]==true`， 所以有`dist[A][A]==true`， 而显然自己不会大于自己， 因此此时存在矛盾。所以判断是否存在矛盾只需要判断是否存在`dist[i][i]==true`即可 - 可以确定两两之间的关系， 判断终止：当所有的变量之间的关系都唯一确定的情况下， 一定有$x_1 < x_2 < \cdots < x_n$， 如果统计对于$x_i$满足$x_i < x_j$的数量， 一定互不相同且遍布$[0, n-1]$的所有值， 此时证明两两之间的关系可以得到确认 - 否则， 在遍历完全部的关系之后， 剩余的情况就是没有矛盾，且不能确定两两之间的关系。 ## AC代码 ```cpp #include <cstdio> #include <cstdlib> #include <iostream> #include <vector> #include <cstring> #include <map> #define endl '\n' using namespace std; const int N = 30, M = 1e5 + 10; int n, m; bool dist[N][N], backup[N][N]; int x[M], y[M]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); while(cin >> n >> m) { memset(backup, 0, sizeof backup); if(n == 0 && m == 0) break; for(int i = 1; i <= m; i ++) { char c1, tmp, c2; cin >> c1 >> tmp >> c2; x[i] = c1 - 'A', y[i] = c2 - 'A'; } bool check = false; for(int t = 1; t <= m; t ++) { map<int, int> cnt2alpha, alpha2cnt; int a = x[t], b = y[t]; backup[a][b] = true; memcpy(dist, backup, sizeof backup); for(int k = 0; k < n; k ++) { for(int i = 0; i < n; i ++) { for(int j = 0; j < n; j ++) { dist[i][j] = (dist[i][j] || (dist[i][k] && dist[k][j])); } } } for(int i = 0; i < n; i ++) { int cnt = 0; for(int j = 0; j < n; j ++) { if(dist[i][j]) cnt ++; } cnt2alpha[cnt] = i; alpha2cnt[i] = cnt; } bool flag = false; for(int i = 0; i < n; i ++) { if(dist[i][i]) { flag = true; break; } } if(flag) { cout << "Inconsistency found after " << t << " relations." << endl; check = true; break; } if(cnt2alpha.size() == n) { cout << "Sorted sequence determined after " << t << " relations: "; for(int i = n - 1; i >= 0; i --) cout << char(cnt2alpha[i] + 'A'); cout << '.' << endl; check = true; break; } } if(!check) { cout << "Sorted sequence cannot be determined." << endl; } } return 0; } ``` 最后修改：2025 年 03 月 19 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏