acwing-343. 排序

发表于 分类于 阅读次数： Waline： 本文字数： 1.5k 阅读时长 ≈ 5 分钟

考点

  • 最短路
  • 传递闭包
  • 拓扑排序

题解

见思路

思路

Floyd传递闭包

对于每个i < j的不等式，令d[i, j] = 1，除此以外的情况均令d[i, j] = 0

使用Floyd算法对d进行传递闭包

传递闭包完成后若存在变量i, j，使得d[i, j]和d[j, i]均为1，说明存在环，关系矛盾：

1
if (f[i][j] == 1 && f[j][i] == 1) return -1;

如果存在变量i, j，使得d[i, j]和d[j, i]均为0，说明不能确定每一对变量之间的大小：

注意要在i != j的情况下判定，因为自己不可能小于自己，d[i, i]应恒为0

1
if (i != j && f[i][j] == 0 && f[j][i] == 0) return 0;

只有对于每队变量i, j，d[i, j]和d[j, i]有且仅有一个为1，才能说明能确定每队变量之间的大小关系。

这里最大的难点其实是如何输出。假设有关系B < A < D < C，通过观察floyd后的结果可以发现：

A B C D
A 1 1
B 1 1 1
C
D 1

关系个数越少的，值越大，根据这个来进行输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;
const int maxn = 30;
int n, m;
int d[maxn][maxn], f[maxn][maxn];

int floyd() {
  memcpy(f, d, sizeof(d));
  for (int k = 0; k < n; ++k) {
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        f[i][j] |= f[i][k] & f[k][j];
        // 存在环，矛盾
        if (f[i][j] == 1 && f[j][i] == 1) return -1;
      }
    }
  }
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      if (i != j && f[i][j] == 0 && f[j][i] == 0) return 0;
    }
  }
  return 1;
}

void print() {
  // pair<字符的关系个数，字符>
  pair<int, char> ans[maxn];
  for (int i = 0; i < n; ++i) ans[i].first = 0, ans[i].second = 'A' + i;
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)
      if (f[i][j]) ++ans[i].first;
  sort(ans, ans + n);
  for (int i = n - 1; i >= 0; --i) cout << ans[i].second;
  puts(".");
}

void work() {
  char s[6];
  memset(d, 0, sizeof(d));
  bool flag = 1;
  for (int u, v, i = 1; i <= m; ++i) {
    scanf("%s", s);
    u = s[0] - 'A', v = s[2] - 'A';
    // 尽管本轮得到了答案，但是要继续读入剩余无用数据
    if (!flag) continue;
    d[u][v] = 1;
    int res = floyd();
    if (res == -1) {
      printf("Inconsistency found after %d relations.\n", i), flag = 0;
    } else if (res == 1) {
      printf("Sorted sequence determined after %d relations: ", i), flag = 0;
      print();
    }
  }
  if (flag) puts("Sorted sequence cannot be determined.");
}

int main() {
  while ((cin >> n >> m) && n) work();
  return 0;
}

拓扑排序

令小于关系抽象为一条有向边，那么题目要求的是一条有向无环且最长路等于n的链式拓扑序列。

如果有环，代表大小关系存在矛盾；如果拓扑序列不唯一，拓扑序列的最长路不等于n。

实现方式如下：

  1. 如果出队元素个数不等于n，说明存在环
  2. 如果最长路不等于n，说明拓扑序列不唯一
  3. 或者，当前队列入度等于0的节点个数是否大于1，大于1说明最长路不可能等于n

最长路

最长路写法，常数稍大但是逻辑好想：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5;
int n, m, tot = -1;
int head[30], ver[maxn], nxt[maxn], edge[maxn];
int tind[maxn], ind[maxn], step[maxn];
string ans;

void add(int u, int v, int w) {
  ver[++tot] = v, edge[tot] = w, nxt[tot] = head[u], head[u] = tot;
}

int toposort() {
  memcpy(tind, ind, sizeof(ind));
  // 每个节点默认的最长路为1，就是它自己
  for (int i = 0; i < n; ++i) step[i] = 1;
  ans = "";
  queue<int> q;
  for (int i = 0; i < n; ++i)
    if (!tind[i]) q.push(i);
  int cnt = 0;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    ++cnt;
    ans += (char)('A' + u);
    for (int i = head[u]; ~i; i = nxt[i]) {
      int v = ver[i];
      if (--tind[v] == 0) q.push(v), step[v] = max(step[v], step[u] + 1);
    }
  }
  // 有环，代表矛盾
  if (cnt < n) return -1;
  int mx = INT_MIN;
  for (int i = 0; i < n; ++i) mx = max(mx, step[i]);
  if (mx == n) return 1;
  return 0;
}

void work() {
  char s[6];
  memset(ind, 0, sizeof(ind)), memset(head, -1, sizeof(head)), tot = -1;
  bool flag = 1;
  for (int u, v, i = 1; i <= m; ++i) {
    scanf("%s", s);
    u = s[0] - 'A', v = s[2] - 'A';
    // 尽管本轮得到了答案，但是要继续读入剩余无用数据
    if (!flag) continue;
    add(u, v, 1), ++ind[v];
    int res = toposort();
    if (res == -1) {
      printf("Inconsistency found after %d relations.\n", i), flag = 0;
    } else if (res == 1) {
      printf("Sorted sequence determined after %d relations: %s.\n", i,
             ans.c_str()),
          flag = 0;
    }
  }
  if (flag) puts("Sorted sequence cannot be determined.");
}

int main() {
  while ((cin >> n >> m) && n) work();
  return 0;
}

判断队列元素个数

判断队列中入度为0的元素个数，但是要注意一个逻辑坑点：

在有环且最长路不等于n的情况下，有环情况的判定的优先级是大于最长路判定的，所以代码中使用flag进行延后：

1
2
3
4
5
6
if (q.size() > 1) flag = 0;
...
// 节点没有全部出队，代表有环
if (cnt < n) return -1;
if (flag && ans.length() == n) return 1;
return 0;

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5;
int n, m, tot = -1;
int head[30], ver[maxn], nxt[maxn], edge[maxn];
int tind[maxn], ind[maxn];
string ans;

void add(int u, int v, int w) {
  ver[++tot] = v, edge[tot] = w, nxt[tot] = head[u], head[u] = tot;
}

int toposort() {
  memcpy(tind, ind, sizeof(ind));
  ans = "";
  queue<int> q;
  for (int i = 0; i < n; ++i)
    if (!tind[i]) q.push(i);
  int cnt = 0;
  bool flag = 1;
  while (!q.empty()) {
    // 同一时刻有多个入度为0的节点，说明拓扑序不唯一，最长路必不可能等于n
    // 但不能直接return 0，同时有环和拓扑序列的情况下，有环的优先级更高
    if (q.size() > 1) flag = 0;
    int u = q.front();
    q.pop();
    ++cnt;
    ans += (char)('A' + u);
    for (int i = head[u]; ~i; i = nxt[i]) {
      int v = ver[i];
      if (--tind[v] == 0) q.push(v);
    }
  }
  // 节点没有全部出队，代表有环
  if (cnt < n) return -1;
  if (flag && ans.length() == n) return 1;
  return 0;
}

void work() {
  char s[6];
  memset(ind, 0, sizeof(ind)), memset(head, -1, sizeof(head)), tot = -1;
  bool flag = 1;
  for (int u, v, i = 1; i <= m; ++i) {
    scanf("%s", s);
    u = s[0] - 'A', v = s[2] - 'A';
    // 尽管本轮得到了答案，但是要继续读入剩余无用数据
    if (!flag) continue;
    add(u, v, 1), ++ind[v];
    int res = toposort();
    if (res == -1) {
      printf("Inconsistency found after %d relations.\n", i), flag = 0;
    } else if (res == 1) {
      printf("Sorted sequence determined after %d relations: %s.\n", i,
             ans.c_str()),
          flag = 0;
    }
  }
  if (flag) puts("Sorted sequence cannot be determined.");
}

int main() {
  while ((cin >> n >> m) && n) work();
  return 0;
}