单/全最短路专题两题

youhualiuh / 2024-07-09 / 原文

floyd算法

它是一个全源最短路用来求任意两个结点之间的最短路复杂度较高,不过容易实现只要不出现负环的情况下是可以进行的

for (k = 1; k <= n; k++) {
  for (x = 1; x <= n; x++) {
    for (y = 1; y <= n; y++) {
      f[x][y] = min(f[x][y], f[x][k] + f[k][y]);
    }
  }
}

这 `F[x][y]`，为不经过 K点的最短路径，而 `[x][k]+[k][y]`，为经过了 K点的最短路

P6464 [传智杯 #2 决赛] 传送门

题意:

n栋教学楼有m条双向通行道路连接,会有一对传送阵直接将距离缩短为0,也可能导致其他教学楼也对此产生影响(会变短)

让你在最优的方案求出最短道路之和

思路:

枚举传送阵,并且去更新每一次的最短路之和,如何更新最短路之和是通过Floyd枚举,其次不难发现i->j它的距离是0如果此距离要更新,那么也就是(

这里是因为k次跳板不过这里是i, j当成跳板因为i和j它成为了一个媒介,i到j是可以直接传送的因此可以不难推出下面这个式子)

dist[k][i] + dist[j][l], dist[k][j] + dist[i][l]在和原有的dist[i][j]比较最短的距离最后比较此时更新完后比较最短路之和的最小值.

来后让我想想这个式子是从何处来的请看Code表演

/*
我们是需要考虑三种情况


直接路径 k 到 l 也就是 dist[k][l]
通过传送阵的路径: 
1- 传送阵从k->i 然后传送阵 i->j 最后 j->l 路径长度dist[k][i] + dist[j][l]

2- 传送阵从k->j 然后传送阵 j->i 最后 i->l 路径长度dist[k][i] + dist[j][l]

然后我们需要比较k l之间的最短距离 也就是三条路径中我去选择最短的那一条
所以利用min函数对三个式子进行判读
*/

但是如果传送阵它的值不是0呢那如何操作那是不是在原有的式子中+w不就行了如此即可

Code:

#include<bits/stdc++.h>
    
using namespace std; 
const int N = 1e2 + 5, M = 3e3 + 5, inf = 1e9;
int n, m, dist[N][N]; 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) { // 初始化距离矩阵，除了自己到自己为0，其他为无穷大
        for (int j = 1; j <= n; j++) {
            if (i != j) dist[i][j] = inf;
        }
    }
    for (int i = 1; i <= m; i++) { //读入数据
        int from, to, w; cin >> from >> to >> w;
        dist[from][to] = w;
        dist[to][from] = w;
    }
    for (int k = 1; k <= n; k++) { //使用Floyd算法计算所有点对之间的最短路径
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
    int res = 0, ans = inf;
    // 尝试在所有可能的楼对之间放置传送门 (i和j)这个循环
    for (int i = 1; i <= n; i++) { 
        for (int j = i + 1; j <= n; j++) {
            res = 0;
            // 计算当前方案下的所有的点最短路径总和 (k, j)
            for (int k = 1; k <= n; k++) { 
                for (int l = k + 1; l <= n; l++) {
                    if (i != k || j != l) {
                        res += min(dist[k][l], min(dist[k][i] + dist[j][l], dist[k][j] + dist[i][l]));
                    }
                }
            }
            // 更新最短路径总和
            ans = min(ans, res);
        }
    }
    cout << ans << '\n';
    return 0;
}

Greg and Graph （Floyd）(这种离线操作很常用)

题意:

Greg 有一个n个点是一个有边权的有向图这个图两个点都有不一样的边(也就意味着 a -> b 和 b -> a的权值是不一样的)

每次操作都会删除一个点,让这个点和其他和它有关系的点都删除.对于每次删除操作,输出操作以前的最短路径之和

思路:

这一题的思路其实与很早之前的并查集删点一样,其实这就是反向加边,通过离线的操作求出最终的答案

可以通过Floyd对于每一次加边跑一次最短路径即可最后输出数组即可

为什么要离线算法是通过这种方法，我们可以避免每次删除一个顶点后重新计算最短路径，反而可以利用已计算的结果逐步更新，效率更高嘿嘿

Code:

#include <bits/stdc++.h>

using namespace std; 
typedef long long ll;
const int N = 5e2 + 5; 
int dist[N][N], n, x[N]; 
ll ans[N];  
bitset<N> vis;  

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n; cin >> n;   
    for (int i = 1; i <= n; i++) { // 输入
        for (int j = 1; j <= n; j++) {
            cin >> dist[i][j];
        }
    } 
    for (int i = 1; i <= n; i++) {
        cin >> x[i]; // 输入删除顺序
        vis[x[i]] = 1; // 标记顶点初始删除
    } 
    for (int tail = n; tail >= 1; tail--) {// 逆序处理删除顺序
        int k = x[tail];
        vis[k] = 0; // 恢复第k个顶点 
        for (int i = 1; i <= n; i++) { // 更新距离矩阵，考虑通过k顶点的最短路径
            for (int j = 1; j <= n; j++) {
                if (i == j) continue;
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); 
                if (!vis[i] && !vis[j]) ans[tail] += dist[i][j]; // 如果i和j都未被删除，累加最短路径
            }
        }
    } 
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << " \n"[i == n];
    }

    return 0;
}