Acwing 343.排序
题意
给定 n 个变量和 m个不等式。其中 n小于等于 26，变量分别用前 n 的大写英文字母表示。
不等式之间具有传递性，即若A>B 且B>C，则 A>C。
请从前往后遍历每对关系，每次遍历时判断：
如果能够确定全部关系且无矛盾，则结束循环，输出确定的次序；
如果发生矛盾，则结束循环，输出有矛盾；
如果循环结束时没有发生上述两种情况，则输出无定解。
思路
对于每个小于关系，用 g[a][b] = 1 表示 a<b ，然后对这个矩阵做一次传递闭包（floyd） 就可以得到每个点之间的关系。
做完传递闭包后会出现以下三种情况：
如果 g[i][i] = 1 表示出现了矛盾 因为 如果存在 a < b，b < c，c < a 那么最后会有 a < a 即 g[a][a] = 1 。
如果存在 g[i][j] == 0 && g[j][i] == 0表示这两个数之间的大小关系还不确定。
否则 不存在矛盾且可以找到每个数之间的大小关系。
代码
#include<bits/stdc++.h> #include<unordered_map> // #define int long long #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3f #define mod 1000000007 #define MOD 998244353 #define rep(i, st, ed) for (int (i) = (st); (i) <= (ed);++(i)) #define pre(i, ed, st) for (int (i) = (ed); (i) >= (st);--(i)) #define endl '\n' #define debug(x,y) cerr << (x) << " == " << (y) << endl; using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; template<typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; } template<typename T> inline T lowbit(T x) { return x & -x; } // template<typename T> T qmi(T a, T b = mod - 2, T p = mod) { T res = 1; b %= (p - 1 == 0 ? p : p - 1); while (b) { if (b & 1) { res = (LL)res * a % p; }b >>= 1; a = (LL)a * a % p; }return res % mod; } const int N = 30; int n, m; int g[N][N], d[N][N]; bool vis[N]; void floyd() { memcpy(g, d, sizeof g); rep(k, 0, n - 1) rep(i, 0, n - 1) rep(j, 0, n - 1) g[i][j] |= g[i][k] & g[k][j]; } int check() { rep(i, 0, n - 1)if (g[i][i])return 2; // 矛盾 // 是否可以确定关系 rep(i, 0, n - 1) { rep(j, i + 1, n - 1) { if (!g[i][j] && !g[j][i])return 0; } } return 1; // 可以确定关系 } char get_min() { // 找一个当前没有遍历过的最小的值 for (int i = 0; i < n; ++i) { if (vis[i])continue; bool flag = true; for (int j = 0; j < n; ++j) { if (vis[j])continue; if (g[j][i]) { // 如果有比 i 更小的 那么i 一定不是最小的 flag = false; break; } } if (flag) { vis[i] = true; return 'A' + i; } } } void solve() { while (cin >> n >> m, n || m) { memset(vis, 0, sizeof vis); memset(g, 0, sizeof g); memset(d, 0, sizeof d); int type = 0; int pos = 0; for (int t = 1; t <= m; ++t) { char str[5]; cin >> str; int a = str[0] - 'A'; int b = str[2] - 'A'; d[a][b] = 1; if (!type) { // 如果还没有确定 确定之后 pos不会改变 floyd(); type = check(); pos = t; } } if (type == 0) { printf("Sorted sequence cannot be determined.\n"); } else if (type == 1) { printf("Sorted sequence determined after %d relations: ", pos); for (int i = 1; i <= n; ++i)printf("%c", get_min()); printf(".\n"); } else if (type == 2) { printf("Inconsistency found after %d relations.\n", pos); } } } signed main() { //int _; cin >> _; //while (_--) solve(); return 0; }
#include<bits/stdc++.h> #include<unordered_map> // #define int long long #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3f #define mod 1000000007 #define MOD 998244353 #define rep(i, st, ed) for (int (i) = (st); (i) <= (ed);++(i)) #define pre(i, ed, st) for (int (i) = (ed); (i) >= (st);--(i)) #define endl '\n' #define debug(x,y) cerr << (x) << " == " << (y) << endl; using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; template<typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; } template<typename T> inline T lowbit(T x) { return x & -x; } // template<typename T> T qmi(T a, T b = mod - 2, T p = mod) { T res = 1; b %= (p - 1 == 0 ? p : p - 1); while (b) { if (b & 1) { res = (LL)res * a % p; }b >>= 1; a = (LL)a * a % p; }return res % mod; } const int N = 30; int n, m; int g[N][N], d[N][N]; bool vis[N]; int check() { rep(i, 0, n - 1)if (g[i][i])return 2; // 矛盾 // 是否可以确定关系 rep(i, 0, n - 1) { rep(j, i + 1, n - 1) { if (!g[i][j] && !g[j][i])return 0; } } return 1; // 可以确定关系 } char get_min() { // 找一个当前没有遍历过的最小的值 for (int i = 0; i < n; ++i) { if (vis[i])continue; bool flag = true; for (int j = 0; j < n; ++j) { if (vis[j])continue; if (g[j][i]) { // 如果有比 i 更小的 那么i 一定不是最小的 flag = false; break; } } if (flag) { vis[i] = true; return 'A' + i; } } } void solve() { while (cin >> n >> m, n || m) { memset(g, 0, sizeof g); memset(d, 0, sizeof d); memset(vis, 0, sizeof vis); int type = 0; int pos = 0; for (int t = 1; t <= m; ++t) { char str[5]; cin >> str; int a = str[0] - 'A'; int b = str[2] - 'A'; if (!type) { // 如果还没有确定 确定之后 pos不会改变 // 如果a能连一条到b的边，那么能到a的点一定可以与b能到的点连一条边 g[a][b] = 1; for(int x = 0 ; x < n ;++x){ // 如果a能连一条到b的边，那么能到a的点，一定可以向b连一条边 // 同理 a一定可以向 b能到的点连一条边 if(g[x][a])g[x][b] = 1; if(g[b][x])g[a][x] = 1; for(int y =0 ; y < n; ++ y){ if(g[x][a] && g[b][y])g[x][y] = 1; } } type = check(); pos = t; } } if (type == 0) { printf("Sorted sequence cannot be determined.\n"); } else if (type == 1) { printf("Sorted sequence determined after %d relations: ", pos); for (int i = 1; i <= n; ++i)printf("%c", get_min()); printf(".\n"); } else if (type == 2) { printf("Inconsistency found after %d relations.\n", pos); } } } signed main() { //int _; cin >> _; //while (_--) solve(); return 0; }
