第三章 图论 No.3 flody之多源汇最短路，传递闭包，最小环与倍增

  • 阿里云国际版折扣https://www.yundadi.com

    • 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6

    文章目录


    flody的四个应用

    1. 多源汇最短路
    2. 传递闭包
    3. 找最小环
    4. 恰好经过k条边的最短路 倍增

    多源汇最短路1125. 牛的旅行

    1125. 牛的旅行 - AcWing题库
    image.png

    直径概念同一连通块中两个距离最远的点之间的距离
    如何求直径由于图中存在着两个连通块所以直接对全图做一个flody就能更新出任意两点间的距离距离大于正无穷的一半时说明两点处于不同连通块中
    题目要连接两个连通块并计算所有连接方法下原连通块与新连通块中最大直径的最小值

    可以枚举所有的连接方式维护出新连通块的直径最小值将其与原连通块的两个直径比较取三者的最小值即可
    假设连接了属于不同连通块的i和j那么经过这条边的直径等于get_dis(i, j) + dmax(i) + dmax(j)其中get_dis表示两点间的距离dmax(i)表示在原连通块中i与距离i最远的点的距离
    那么新连通块的直径是原连通块的直径与经过连接两连通块的边的直径中的最大值

    最终要在原连通块的直径与新连通块的直径最大值中取min
    在计算新连通块的直径最大值时需要在原连通块与当前新连通块的直径中取max由于每中不同连接方式都要与原连通块的直径取max我们可以放到最后在与之取max
    先计算经过连接两连通块的边的直径的最大值在与原连通块的直接取max

    #include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>

#define x first
#define y second

using namespace std;

typedef pair<double, double> PDD;

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

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

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

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> q[i].x >> q[i].y;
    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]);
            else d[i][j] = INF;

    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)
                maxd[i] = max(maxd[i], d[i][j]);
        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)
                r2 = min(r2, maxd[i] + maxd[j] + get_dist(q[i], q[j]));
cout << r1 << ' ' << r2 << endl;
    printf("%.6lf\n", max(r1, r2));

    return 0;
}

    传递闭包343. 排序

    343. 排序 - AcWing题库
    image.png

    将简洁相连的点连接起来成为传递闭包
    用flody可以在 O ( n 3 ) O(n^3) O(n3)的时间复杂度内计算出传递闭包
    用邻接矩阵g存储图传递闭包保存在矩阵d上
    g[i][j]为1表示存在一条从i到j的边g[i][j]为0表示不存在
    初始化d[i][j] = g[i][j]
    flody的更新换为
    d[i][j] |= d[i][k] && d[k][j]

    image.png

    题目中的小于关系就是一条边每次读取一个小于关系就在图中添加一条边然后求传递闭包
    三种情况

    1. 矛盾此时d[i][[i] = 1表示i存在自环。因为d[i][j] == 1 && d[j][i] == 1求完传递闭包后d[i][i] = 1
    2. 情况未确定d[i][j]和d[j][i]都为0表示i和j之间没有边即没有小于关系
    3. 情况确定遍历完d数组无以上情况此时情况确定

    当情况确定时如何按小于关系输出变量 O ( n 2 ) O(n^2) O(n2)地暴力搜索所有点将已经输出的变量进行标记若当前点是某一条边的终点并且起点未被标记说明存在小于当前变量的变量且未被输出
    若当前变量不是任意一条边的终点或者起点已经被标记那么输出该变量并标记

    #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;
}

    最小环344. 观光之旅

    344. 观光之旅 - AcWing题库
    image.png

    如何求第k类的最小环
    思考flody的三重循环在第一重k循环时我们已经知道从i到j只经过1~k-1这些点的最短路径
    若ijk三者能构成环那么i和k直接相连i和j也直接相连
    image.png

    此时ijk构成的最小环的长度就等于d[i][j] + g[i][k] + g[k][j]
    d[i][j]为i到j的最短距离
    所以在循环k时就可以枚举所有的i和j得到包含ijk三点的最小环在这些最小环中取min即可

    此外还需要求具体方案
    只需要在更新的时候d[i][j] > d[i][k] + d[k][j]时记录i到j的最短路经过了k即可即pos[i][j] = k
    求i到j的最短路时采用递归的方式get_path(i, j)该函数将顺序输出i到j的最短路中除了i和j的所有中间点
    get_path(i, j)通过pos[i][j]的值将i到j划分称i到k到j递归get_path(i, k)与get_path(k, j)直到pos[i][j]为0说明i到j之间无之间点即两点之间相连

    #include <iostream>
#include <cstring>
using namespace std;

typedef long long LL;
const int N = 110, M = 20010, INF = 0x3f3f3f3f;
int g[N][N], d[N][N];
int path[N], cnt;
int pos[N][N];
int n, m;

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()
{
    scanf("%d%d", &n, &m);
    memset(g, 0x3f, sizeof(g));
    for (int i = 1; i <= n; ++ i ) g[i][i] = 0;
    for (int i = 1; i <= m; ++ i )
    {
        int x, y, d;
        scanf("%d%d%d", &x, &y, &d);
        g[x][y] = g[y][x] = min(g[x][y], d);
    }
    
    memcpy(d, g, sizeof(g));
    int res = INF;
    for (int k = 1; k <= n; ++ k )
    {
        for (int i = 1; i < k; ++ i  )
            for (int j = i + 1; j < k; ++ j )
            {
                if (res > (LL)d[i][j] + g[i][k] + g[k][j])
                {
                    res = d[i][j] + g[i][k] + g[k][j];
                    cnt = 0;
                    path[cnt ++ ] = k; // 从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 ) printf("%d ", path[i]);
        
    return 0;
}

    一些需要注意的地方res > (LL)d[i][j] + g[i][k] + g[k][j]
    不开LL的话可能三个INF相加会导致爆int
    枚举最小环时j从i+1开始保证j比i的同时也保证最小环中至少有三个点

    没看懂先跳过

    345. 牛站

    345. 牛站 - AcWing题库
    image.png

    flody的变形表示的状态发生变化 f ( k , i , j ) f(k, i, j) f(k,i,j)表示从i到j恰好经过k条边的最短路
    d [ a + b , i , j ] = d [ a , i , k ] + d [ b , k , j ] d[a+b, i, j] = d[a, i, k] + d[b, k, j] d[a+b,i,j]=d[a,i,k]+d[b,k,j]
    从i到j恰好经过a+b条边的最短路径假设中间点为k将路径划分称两段经过a条边从i到k经过b条边从k到j。两段分别取最短路径相加得到我们需要的最短路径
    枚举所有的k取min后就能得到 d [ a + b , i , j ] d[a+b, i, j] d[a+b,i,j]
    枚举所有的k后枚举不同的i和j转换成代码就是flody的形式

    image.png

  • 阿里云国际版折扣https://www.yundadi.com

    • 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6
    返回列表

    上一篇：nnU-Net 终极指南

    下一篇：【Linux】深入理解进程概念

    “第三章 图论 No.3 flody之多源汇最短路，传递闭包，最小环与倍增” 的相关文章

    Android8.1 系统设置默认值大全1年前 (2023-02-02)
    SpringCloud详解1年前 (2023-02-02)
    浅谈服务接口的高可用设计1年前 (2023-02-02)
    如何做研发效能提升1年前 (2023-02-02)
    MySQL高可用之主备同步：MySQL是如何保证主备一致的_mysql 主备同步日志1年前 (2023-02-02)
    WebSocket1年前 (2023-02-02)
    【算法训练营day27】LeetCode39. 组合总和 LeetCode40. 组合总和II LeetCode131. 分割回文串1年前 (2023-02-02)
    这可是全网eNSP安装最完整，最详细的图解，没有之一（安装步骤）_ensp安装1年前 (2023-02-02)
    SpringMVC学习笔记1年前 (2023-02-02)
    Java多线程-线程的创建(Thread类的基本使用)1年前 (2023-02-02)

    阿里云国际版