SpringApplication 多线程 jsp Transformer join compilation gtk vue组件开发 管理后台模板 jquery查找子元素 jquery解析json bootstrap中文api文档 mysql倒序 vm虚拟化引擎 网络游戏server编程 pcie转sata mac脚本编辑器 solidworks图库 axure导出html文件 linuxmysql启动命令 python获取日期 python操作mysql python学习文档 java的集合框架 java环境包 真实女友补丁 方正兰亭字体下载 3d软件下载 凤凰刷机 diskman 五子棋大师 fireworks序列号 抽出滤镜下载 数据库建模工具 spring拦截器 csgo帧数显示 python保存文件 ps智能参考线 昌江县干部在线学习 pr时间轴不见了
当前位置: 首页 > 学习教程  > 编程语言

AcWing 343. 排序(传递闭包)

2020/9/19 14:47:08 文章标签:

题目

给定 n 个变量和 m 个不等式。其中 n 小于等于26,变量分别用前 n 的大写英文字母表示。

不等式之间具有传递性,即若 A>B 且 B>C ,则 A>C。

请从前往后遍历每对关系,每次遍历时判断:

如果能够确定全部关系且无矛盾,则结束循环,输出确定的次序;
如果发生矛盾,则结束循环,输出有矛盾;
如果循环结束时没有发生上述两种情况,则输出无定解。
输入格式
输入包含多组测试数据。

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

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

当输入一行0 0时,表示输入终止。

输出格式
每组数据输出一个占一行的结果。

结果可能为下列三种之一:

如果可以确定两两之间的关系,则输出 “Sorted sequence determined after t relations: yyy…y.”,其中’t’指迭代次数,'yyy…y’是指升序排列的所有变量。
如果有矛盾,则输出: “Inconsistency found after t relations.”,其中’t’指迭代次数。
如果没有矛盾,且不能确定两两之间的关系,则输出 “Sorted sequence cannot be determined.”。
数据范围
2≤n≤26,变量只可能为大写字母A~Z。

输入样例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.
难度:简单
时/空限制:1s / 10MB
总通过数:1104
总尝试数:2616
来源:《算法竞赛进阶指南》
算法标签

思路

  • 假设d[i][j]=1表示i<j,=0表示i,j没有关系,那么判断一个序列是否能唯一确定排序,只要看一下是不是任意两点的关系都确定了,也就是对于d[i][j]和d[j][i]只能并且必须有一个为1,所以这里可以用Floyd来求每一次加一条边进去的情况,最后如果存在自环也就是d[i][i]=1则有矛盾,如果不是任意两点满足d[i][j]和d[j][i]只能并且必须有一个为1的条件,就是不能确定,如果都确定了就是能唯一排序了
  • 能唯一排序后每一次取出全部没有被排序的数中最小的值,一个数字如果最小那么它肯定对于全部没有被排序的数来说,没有一个可以到达的,即d[i][j]为0,这样就可以求出来最小值
  • 复杂度 O(mn^3)
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 26;

int n, m;
bool g[N][N], d[N][N];
bool st[N];

void floyd()
{
    memcpy(d, g, sizeof d);

    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 ++ )
        if (d[i][i])
            return 2;

    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < i; j ++ )
            if (!d[i][j] && !d[j][i])
                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(g, 0, sizeof g);
        int type = 0, t;
        for (int i = 1; i <= m; i ++ )
        {
            char str[5];
            cin >> str;
            int a = str[0] - 'A', b = str[2] - 'A';

            if (!type)
            {
                g[a][b] = 1;
                floyd();
                type = check();
                if (type) t = i;
            }
        }

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

    return 0;
}


增量优化

  • 由于每一次加边不用都用一次Floyd,因为没加入一条i到j的边,可以带来的所有更新关系只有一下几种
    • ①:a可以到i,则d[a][j]=1
    • ②:j可以到b,则d[i][b]=1
    • ③:a可以到i,b可以到j,则d[a][b]=1
    • 每一次加入着三种边即可
  • 复杂度O(m*n^2)
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 26;

int n, m;
bool d[N][N];
bool st[N];

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

    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < i; j ++ )
            if (!d[i][j] && !d[j][i])
                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);

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

            if (!type)
            {
                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;
                }
                type = check();
                if (type) t = i;
            }
        }

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

    return 0;
}


本文链接: http://www.dtmao.cc/news_show_200179.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?