• 【图论】Floyd

    算法提高课笔记）

    文章目录

    例题

    牛的旅行

    原题链接

    农民John的农场里有很多牧区，有的路径连接一些特定的牧区。

    一片所有连通的牧区称为一个牧场。

    但是就目前而言，你能看到至少有两个牧区不连通。

    现在，John想在农场里添加一条路径（注意，恰好一条）。

    一个牧场的直径就是牧场中最远的两个牧区的距离（本题中所提到的所有距离指的都是最短的距离）。

    考虑如下的两个牧场，每一个牧区都有自己的坐标：
    在这里插入图片描述

    图 1 是有 5 个牧区的牧场，牧区用“*”表示，路径用直线表示。

    图 1 所示的牧场的直径大约是 12.07106, 最远的两个牧区是 A 和 E，它们之间的最短路径是 A-B-E。

    图 2 是另一个牧场。

    这两个牧场都在John的农场上。

    John将会在两个牧场中各选一个牧区，然后用一条路径连起来，使得连通后这个新的更大的牧场有最小的直径。

    注意，如果两条路径中途相交，我们不认为它们是连通的。

    只有两条路径在同一个牧区相交，我们才认为它们是连通的。

    现在请你编程找出一条连接两个不同牧场的路径，使得连上这条路径后，所有牧场（生成的新牧场和原有牧场）中直径最大的牧场的直径尽可能小。

    输出这个直径最小可能值。

    输入格式

    第 1 行：一个整数 N, 表示牧区数；

    第 2 到 N+1 行：每行两个整数 X,Y， 表示 N 个牧区的坐标。每个牧区的坐标都是不一样的。

    第 N+2 行到第 2*N+1 行：每行包括 N 个数字 ( 0或1 ) 表示一个对称邻接矩阵。

    例如，题目描述中的两个牧场的矩阵描述如下：

      A B C D E F G H 
A 0 1 0 0 0 0 0 0 
B 1 0 1 1 1 0 0 0 
C 0 1 0 0 1 0 0 0 
D 0 1 0 0 1 0 0 0 
E 0 1 1 1 0 0 0 0 
F 0 0 0 0 0 0 1 0 
G 0 0 0 0 0 1 0 1 
H 0 0 0 0 0 0 1 0

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    输入数据中至少包括两个不连通的牧区。

    输出格式

    只有一行，包括一个实数，表示所求答案。

    数字保留六位小数。

    数据范围

    1 ≤ N ≤ 150 , 1≤N≤150, 1≤N≤150,
    0 ≤ X , Y ≤ 105 0≤X,Y≤105 0≤X,Y≤105

    输入样例

    8
10 10
15 10
20 10
15 15
20 15
30 15
25 10
30 10
01000000
10111000
01001000
01001000
01110000
00000010
00000101
00000010

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    输出样例

    22.071068

    • 1

    题意

    给出一张图，连通的部分算作一个区域，每个区域的直径为区域中相隔最远的两个点的距离，问在不同区域中添加一条边，得到的最小直径是多少

    思路

    先建图，然后跑一遍floyd算出和每一个点相隔最远的点的距离

    得到的最新直径一定大于等于原来的最大直径，因此可以先求出原来的最大直径maxd[i]

    加上一条边[i, j]得到的新直径是maxd[i] + maxd[j] + dist[i][j]

    二者取最大值即可

    代码

    #include 

using namespace std;

typedef pair<double, double> PDD;

const int N = 155;
const double INF = 1e20;

int n;
double d[N][N];
double maxd[N];
char g[N][N];
PDD q[N];

double get_dist(PDD a, PDD b)
{
    double dx = a.first - b.first;
    double dy = a.second - b.second;
    return sqrt(dx * dx + dy * dy);
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> q[i].first >> q[i].second;
    for (int i = 0; i < n; i ++ ) cin >> g[i];

    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            if (i == j) d[i][j] = 0;
            else if (g[i][j] == '1') d[i][j] = get_dist(q[i], q[j]); // ij之间有边
            else d[i][j] = INF; // ij之间无边

    // 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] = min(d[i][j], d[i][k] + d[k][j]);

    double r1 = 0; // 两个牧场中最长的直径
    for (int i = 0; i < n; i ++ )
    {
        for (int j = 0; j < n; j ++ )
            if (d[i][j] < INF / 2) // 说明ij之间有边
                maxd[i] = max(maxd[i], d[i][j]); // 更新与i最远的点距离
        r1 = max(r1, maxd[i]); // 更新直径
    }

    double r2 = INF; // 加边之后的最长值
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            if (d[i][j] > INF / 2) // 说明ij之间无边 可以加边
                r2 = min(r2, maxd[i] + maxd[j] + get_dist(q[i], q[j]));
    
    printf("%.6lf\n", max(r1, r2));
}

    • 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

    排序

    原题链接

    给定 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 。 2≤n≤26，变量只可能为大写字母 A∼Z。 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
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    输出样例1

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

    • 1
    • 2
    • 3

    输入样例2

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    输出样例2

    Inconsistency found after 6 relations.

    • 1

    输入样例3

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    输出样例3

    Sorted sequence determined after 4 relations: ABCDE.

    • 1

    题意

    从前到后遍历给出的关系，如果能确定所有关系就直接输出当前次数和关系，如果前后矛盾则输出矛盾，如果得不到最终关系就输出得不到最终关系

    思路

    传递闭包

    已知a>b b>c 一定可以推出 a>c，根据这个性质，我们可以在得到每个新的判断时进行传递，看看是否不满足原先已知的结论，如果不满足就会出现i和i的关系确定的结果

    代码

    #include 

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]; // 如果有i->k k->j的边 那就加上i->j的边
}

int check()
{
    for (int i = 0; i < n; i ++ )
        if (d[i][i]) return 2; // 出现矛盾返回2

    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < i; j ++ )
            if (!d[i][j] && !d[j][i])
                return 0; // 遍历所有数对 没确定返回0

    return 1; // 确定就返回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]) // 如果有没出现过的j比i还小的话说明i不是最小值
                {
                    flag = false;
                    break;
                }
            if (flag) // 否则i就是当前没出现过的数中的最小值
            {
                st[i] = true;
                return 'A' + i;
            }
        }
}

int main()
{
    while (cin >> n >> m, n || m)
    {
        memset(g, 0, sizeof g);
        int type = 0, t; // type表示目前关系未确定/确定/矛盾
        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; // t记录经过几次才确定所有关系
            }
        }

        if (!type) puts("Sorted sequence cannot be determined."); // 关系不确定
        else if (type == 2) cout << "Inconsistency found after " << t << " relations.\n"; // 矛盾
        else // 确定
        {
            memset(st, 0, sizeof st);
            cout << "Sorted sequence determined after " << t << " relations: ";
            for (int i = 0; i < n; i ++ ) cout << get_min();
            cout << ".\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
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85

    观光之旅

    原题链接

    给定一张无向图，求图中一个至少包含 3 个点的环，环上的节点不重复，并且环上的边的长度之和最小。

    该问题称为无向图的最小环问题。

    你需要输出最小环的方案，若最小环不唯一，输出任意一个均可。

    输入格式

    第一行包含两个整数 N 和 M，表示无向图有 N 个点，M 条边。

    接下来 M 行，每行包含三个整数 u，v，l，表示点 u 和点 v 之间有一条边，边长为 l。

    输出格式

    输出占一行，包含最小环的所有节点（按顺序输出），如果不存在则输出 No solution.。

    数据范围

    1 ≤ N ≤ 100 , 1≤N≤100, 1≤N≤100,
    1 ≤ M ≤ 10000 , 1≤M≤10000, 1≤M≤10000,
    1 ≤ l < 500 1≤l<500 1≤l<500

    输入样例

    5 7
1 4 1
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    输出样例

    1 3 5 2

    • 1

    题意

    无向图的最小环裸题

    思路

    假设环的形式是这样的：（ij均小于k）
    在这里插入图片描述
    那么环的长度就是d[i][j] + g[j][k] + g[k][i]（d代表ij在图上的最短距离，g表示两点之间有边的话 边的长度）

    用pos[i][j] = k记录i和j的最短路由k的状态转移，k是路径中编号最大的点

    在floyd中循环每个k，如果d[i][j] + g[j][k] + g[k][i]比当前的最小环长度更小就更新一下

    使用类似中序遍历的算法求出环中的字母

    代码

    #include 

using namespace std;

typedef long long ll;

const int N = 110, INF = 0x3f3f3f3f;

int n, m;
int d[N][N], g[N][N];
int pos[N][N];
int path[N], cnt;

void get_path(int i, int j)
{
    if (pos[i][j] == 0) return;

    // 类似于中序遍历
    int k = pos[i][j];
    get_path(i, k);
    path[cnt ++ ] = k;
    get_path(k, j);
}

int main()
{
    cin >> n >> m;
    
    memset(g, 0x3f3f3f3f, sizeof g);
    for (int i = 1; i <= n; i ++ ) g[i][i] = 0; // 避免统计自环

    while (m -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c);
    }

    int res = INF;
    memcpy(d, g, sizeof d);
    for (int k = 1; k <= n; k ++ )
    {
        for (int i = 1; i < k; i ++ )
            for (int j = i + 1; j < k; j ++ )
                if ((ll)d[i][j] + g[j][k] + g[k][i] < res) // 一旦发现比原来的最短路还要短的路径就更新
                {
                    res = d[i][j] + g[j][k] + g[k][i]; // 最短路长度
                    // 更新最短路中的点
                    cnt = 0;
                    path[cnt ++ ] = k;
                    path[cnt ++ ] = i;
                    get_path(i, j);
                    path[cnt ++ ] = j;
                }

        // 更新两点之间的距离 在更新完最小环之后更新所以不会对最小环有影响
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                if (d[i][j] > d[i][k] + d[k][j])
                {
                    d[i][j] = d[i][k] + d[k][j];
                    pos[i][j] = k;
                }
    }

    if (res == INF) puts("No solution.");
    else
    {
        for (int i = 0; i < cnt; i ++ ) cout << path[i] << ' ';
        cout << '\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
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
  • 相关阅读:
    格芯斥资80亿欧元，提高德国德累斯顿的产能，并寻求与台积电相当的政府补贴
    iOS AVPlayer
    水文-ts中对中文进行base64编码
    ubuntu vbox 5.2 资源 virtualbox-dkms
    TCP/IP网络编程：P3-＞地址族与数据序列
    只出现一次的数字Ⅱ
    CSP2022
    vue源码解析---AST抽象语法树
    AndroidStudio添加一个虚拟设备
    Java虚拟机
  • 原文地址：https://blog.csdn.net/dhxbshbdjzxy/article/details/132782369