🪴 Edwin Aze's Blog

最近文章

最近笔记

排序

6分钟阅读

343. 排序 - AcWing题库 #floyd求传递闭包 T3 给定 个变量和 个不等式。其中 小于等于 ，变量分别用前 的大写英文字母表示。

不等式之间具有传递性，即若 且 ，则 。

请从前往后遍历每对关系，每次遍历时判断：

  • 如果能够确定全部关系且无矛盾，则结束循环，输出确定的次序；
  • 如果发生矛盾，则结束循环，输出有矛盾；
  • 如果循环结束时没有发生上述两种情况，则输出无定解。

输入格式

输入包含多组测试数据。

每组测试数据，第一行包含两个整数 和 。

接下来 行，每行包含一个不等式，不等式全部为小于关系。

当输入一行 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."。

数据范围

，变量只可能为大写字母 。

输入样例1：

4 6
A<B
A<C
B<C
C<D
B<D
A<B
3 2
A<B
B<A
26 1
A<Z
0 0

输出样例1：

Sorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined.

输入样例2：

6 6
A<F
B<D
C<E
F<D
D<E
E<F
0 0

输出样例2：

Inconsistency found after 6 relations.

输入样例3：

5 5
A<B
B<C
C<D
D<E
E<A
0 0

输出样例3：

Sorted sequence determined after 4 relations: ABCDE.

思路

对于A < B, 就把 A 和 B连一条A→B有向边, 因为小于号具有传递性, 即 A<B, B<C, 则 A<C, 在图上则为： 也就是说, 我们需要让该图成为 传递闭包, 即若 A→B, 则将B能到达的点都与A连边。

floyd算法可以实现这个操作, 只需要状态更新时, 更改为：

dist[i][j] |= dist[i][k] && dist[k][j];

若i→k, k→j存在, 则连一条 i→j 的边。

那么对应题目的情况就是：

  • 无解：存在自环, i→i
  • 确定：对于任意两个点i,j, 存在 i→j 或 j→i
  • 暂不确定：存在两个点i,j, 使得 i→j 与 j→i 均不存在

程序流程： 先读入n,m 然后每读入一个表达式, 就算一次当前的传递闭包, 并判断当前有界情况。

代码

#define S second
#define F first
#define pb push_back
#define pf push_front
#define lson l, mid, u << 1
#define rson mid + 1, r, u << 1 | 1
#define MID l + r >> 1
#define mem(x, n) memset(x, n, sizeof x)
#define setPrec(n) cout << fixed << setpricision(n)
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
using i64 = long long;
// #define debug
const int N = 27;
int n, m;
int g[N][N];
int dist[N][N];
bool st[N];
 
int check()
{
    for (int i = 0; i < n; i++)
        if (dist[i][i])
            return 2;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < i; j++)
            if (!dist[i][j] && !dist[j][i])
                return 0;
    return 1;
}
 
void floyd()
{
    memcpy(dist, g, sizeof dist);
    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][k] && dist[k][j];
}
 
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] && dist[j][i])
                {
                    flag = false;
                    break;
                }
            if (flag)
            {
                st[i] = true;
                return char(i + 'A');
            }
        }
    }
    return 0;
}
 
void solve()
{
    mem(g, 0);
    int t = 0;
    int type = 0;
    for (int i = 1; i <= m; i++)
    {
        char s[5];
        cin >> s;
        int a = s[0] - 'A', b = s[2] - 'A';
        if (!type)
        {
            g[a][b] = 1;
            floyd();
            type = check();
            if (type)
                t = i;
        }
    }
    if (!type)
        printf("Sorted sequence cannot be determined.\n");
    else if (type == 2)
        printf("Inconsistency found after %d relations.\n", t);
    else
    {
        printf("Sorted sequence determined after %d relations: ", t);
        mem(st, 0);
        for (int i = 0; i < n; i++)
            printf("%c", get_min());
        printf(".\n");
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    while (cin >> n >> m, n || m)
    {
        solve();
    }
    return 0;
}

反向链接