AcWing 343. 排序

问题描述

link

分析

题目给 $n$ 个变量（$A,B,C,\dots$）和 $m$ 条形如 X < Y 的大小关系，要求按输入顺序逐条加入关系，并在出现以下三种情况的最早时刻停下来：

1. 关系之间出现矛盾（例如能同时推出 $A<B$ 和 $B<A$）；
2. 能唯一确定所有 $n$ 个变量的总顺序；
3. 全部 $m$ 条关系处理完仍无法确定顺序。

关键建模：把每条关系 $X<Y$ 看成从 $X$ 指向 $Y$ 的一条有向边，那么"能推出的所有大小关系"就是这张图的传递闭包。记 $d[i][j]=1$ 表示能推出 $i<j$（即 $i$ 能到达 $j$），维护好闭包后，三种情况的判定变得非常简洁：

• 矛盾 $⟺$ 图中出现环 $⟺$ 存在 $i\ne j$ 使 $d[i][j]=1$ 且 $d[j][i]=1$；
• 能唯一确定顺序 $⟺$ 任意两个不同变量都可比较，即对一切 $i\ne j$ 有 $d[i][j]=1$ 或 $d[j][i]=1$（只要有一对不可比，就至少存在两种合法的线性顺序）；
• 否则说明当前信息不足，需要继续读入下一条关系。

一旦确定了唯一顺序，输出方式为：不断从未标记的变量中选出"没有未标记前驱"的最小者（即不存在 $j$ 使 $d[j][i]=1$），依次输出。由于此时任意两点可比且无环，得到的顺序是唯一的。

思路一：Floyd 传递闭包（朴素）

每加入一条关系 $a<b$，先令 $d[a][b]=1$，再跑一遍 Floyd 求闭包：

$d[i][j]=d[i][j]\vee (d[i][k]\wedge d[k][j])$

然后用 check() 判定当前状态：先查是否有环（矛盾，返回 $2$），再查是否所有点对都可比（确定，返回 $1$），否则返回 $0$。一旦 $t\ne 0$ 就记录关系编号 $c$，此后剩余关系只读入、不再参与更新。

正确性：Floyd 求出的是可达性闭包，$d[i][j]=1$ 当且仅当 $i<j$ 能由已有关系推出，上述两个判定条件与题意一一对应。

复杂度：$O(m\cdot n^3)$，本题 $n\le 26$，完全可行。

思路二：增量更新（优化）

新加入的边 $a\to b$ 只会产生"经过这条新边"的新路径：若原来已有 $x\to a$ 和 $b\to y$，现在就能推出 $x\to y$。在原闭包已经完整的前提下，只需一趟更新：

• 若 $d[x][a]=1$，则 $d[x][b]=1$（路径 $x\to a\to b$）；
• 若 $d[b][x]=1$，则 $d[a][x]=1$（路径 $a\to b\to x$）；
• 对任意 $x,y$，若 $d[x][a]=1$ 且 $d[b][y]=1$，则 $d[x][y]=1$。

因为 $d[a][a]$、$d[b][b]$ 本身为 $0$，前两条恰好补上 $y=b$ 与 $x=a$ 的边界情况。每加入一条关系只需 $O(n^2)$ 时间，总复杂度 $O(m\cdot n^2)$；判定与输出的部分和思路一完全相同。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N = 26;
int d[N][N], st[N];
int n, m;

void floyd() {
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                d[i][j] |= d[i][k] && d[k][j];
            }
        }
    }
}

int check() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (d[i][j] == 1 && d[j][i] == 1) return 2;
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (d[i][j] == 0 && d[j][i] == 0) return 0;
        }
    }

    return 1;
}

char get_min() {
    for (int i = 0; i < n; i++) {
        if (!st[i]) {
            bool flag = true;
            for (int j = 0; j < n; j++) {
                if (!st[j] && d[j][i]) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                st[i] = true;
                return 'A' + i;
            }
        }
    }
}

int main() {
    while (cin >> n >> m, n || m) {
        memset(d, 0, sizeof d);

        // t: 0 不能确定关系 1 c 次之后能确定关系 2 c 次之后有矛盾
        int t = 0, c;

        for (int i = 1; i <= m; i++) {
            char s[5]; cin >> s;
            int a = s[0] - 'A', b = s[2] - 'A';

            if (!t) {
                d[a][b] = 1;

                floyd();

                t = check();
                if (t) c = i;
            }
        }

        if (!t) puts("Sorted sequence cannot be determined.");
        else if (t == 2) printf("Inconsistency found after %d relations.\n", c);
        else {
            printf("Sorted sequence determined after %d relations: ", c);
            memset(st, 0, sizeof st);
            for (int i = 0; i < n; i++) printf("%c", get_min());
            puts(".");
        }
    }

    return 0;
}

优化

#include <bits/stdc++.h>
using namespace std;

const int N = 26;
int d[N][N], st[N];
int n, m;

int check() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (d[i][j] == 1 && d[j][i] == 1) return 2;
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (d[i][j] == 0 && d[j][i] == 0) return 0;
        }
    }

    return 1;
}

char get_min() {
    for (int i = 0; i < n; i++) {
        if (!st[i]) {
            bool flag = true;
            for (int j = 0; j < n; j++) {
                if (!st[j] && d[j][i]) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                st[i] = true;
                return 'A' + i;
            }
        }
    }
}

int main() {
    while (cin >> n >> m, n || m) {
        memset(d, 0, sizeof d);

        // t: 0 不能确定关系 1 c 次之后能确定关系 2 c 次之后有矛盾
        int t = 0, c;

        for (int i = 1; i <= m; i++) {
            char s[5]; cin >> s;
            int a = s[0] - 'A', b = s[2] - 'A';

            if (!t) {
                d[a][b] = 1;

                // 优化：只更新当前关系，不更新所有关系
                for (int x = 0; x < n; x ++ ) {
                    if (d[x][a]) d[x][b] = 1;
                    if (d[b][x]) d[a][x] = 1;
                    for (int y = 0; y < n; y ++ ) {
                        if (d[x][a] && d[b][y]) d[x][y] = 1;
                    }
                }

                t = check();
                if (t) c = i;
            }
        }

        if (!t) puts("Sorted sequence cannot be determined.");
        else if (t == 2) printf("Inconsistency found after %d relations.\n", c);
        else {
            printf("Sorted sequence determined after %d relations: ", c);
            memset(st, 0, sizeof st);
            for (int i = 0; i < n; i++) printf("%c", get_min());
            puts(".");
        }
    }

    return 0;
}