🪴 Edwin Aze's Blog

最近文章

最近笔记

多源最短路

8分钟阅读

模板Page Hopping - UVA 821

题目

二基楼有n个教室（1≤n≤100），任意两间教室之间可能存在多条路径（一个你所不知道的世界）。作为一个作死的冒险家，你想走遍所有路径以得到任意两间教室之间最短路径的平均值。最后你得到了结果满意地在二基楼迷了路。

多组数据。 每组数据为一行。一组数据包含多个整数对a、b（1≤a, b≤100），表示可以从教室a到教室b。当输入“0 0”时，表示结束该组数据的输入。 最后输入“0 0”，表示整个输入的结束。

每组数据输出一行。以Sample Output的格式输出任意两教室最短距离的平均值，保留3位小数。

input

1 2 2 4 1 3 3 1 4 3 0 0
1 2 1 4 4 2 2 7 7 1 0 0
0 0

output

Case 1: average length between pages = 1.833 clicks
Case 2: average length between pages = 1.750 clicks

hits 第一组数据中，路径有12条，其总的最短路径长度为22，则平均值为22/12=1.833

思路

求所有最短路径长度的平均值, 那就要知道每个点能去的点数量（路径数）和每个点能去的点之间的路径和。

显然我们需要多次求两个点之间的最短路径, 最符合的算法就是 floyd 求多源最短路。 求出来最短路之后就再次遍历所有点, 若他们之间的最短路径存在则说明是一个成立的路径, 用这种方法来求出所有路径数。 最后输出即可。

代码

//          Made by Aze         //
//------------------------------//
/*
 *    problem:https://vjudge.csgrandeur.cn/problem/UVA-821#author=SCU2018
 *    date:8/17 2:48PM
 *
 */
 
//------- Include Area----------//
 
#include <iostream>
#include <iomanip>
#include <cstring>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
 
int readInt()
{
    int t;
    cin >> t;
    return t;
}
 
//------- Coding Area ---------//
const int N = 1010, INF = 0x3f3f3f3f;
 
int dist[N][N];
int n;
 
void floyd()
{
    for (int k = 1; k <= n; k++)
        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 main()
{
    cin.tie(0)->sync_with_stdio(false);
    cout << fixed << setprecision(3); // 浮点数精度设置为保留小数点后3位
    
    int a, b;
    int kase = 1;
    while (cin >> a >> b && (a || b))
    {
        memset(dist, INF, sizeof dist);
        do
        {
            dist[a][b] = 1;
            n = max(n, a);
            n = max(n, b);
        } while (cin >> a >> b && (a || b));
        floyd();
        double res = 0;
        int cnt = 0;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (j != i && dist[i][j] != INF)
                {
                    cnt++;
                    res += dist[i][j];
                }
            }
        }
        cout << "Case " << kase++ << ": average length between pages = " << res / (double)cnt << " clicks\n";
    }
 
    return 0;
}

多源路径最大值最小Audiophobia

题目

Alice喜欢冒险。现在Alice在一座小岛上，这座岛有许多站，各站之间有些存在着通路，但通路中间有石墙阻挡。Alice可以借助自己随身携带的绳索翻过石墙从而能从一站到达另一站。绳索的长度为L，则所有高度不大于L的石墙Alice都可以翻过。不过绳索是特种工具，太长的绳索重量很大难以携带，Alice希望能尽量短地拿一根绳索并到达目的地。给出Alice的起点和终点，帮助Alice确定最短能完成冒险的绳索长度。

多组数据。 每组数据有多行，第一行是三个用空格分隔的数字C，S，Q，分别表示有C个小站，S条通路和Q次冒险。接下来有S行，每行有三个数字由空格隔开，分别是c1,c2,d，表示从c1站到c2站（c1 ≠ c2）有通路，并且中间有高为d的石墙。接下来Q行，一行中给出两个整数c1,c2，表示Alice的探险要从c1到c2（c1 ≠ c2）。
数据最后一行C，S，Q都是0，表示数据输入结束，这一组数据不需要处理

  • C ≤ 100
  • S ≤ 1000
  • Q ≤ 10000
  • 0 < d ≤ 100000
  • 1 ≤ c1,c2 ≤ C

对于每组数据，先在一行中输出编号（从1开始），接下来输出Q行，输出一个数字表示这一个冒险中Alice可带的最短绳子的长度，若Alice选的这两站之间不能连通，则输出”no path”。
每两组数据之间用一个空行隔开。

input

7 9 3
1 2 50
1 3 60
2 4 120
2 5 90
3 6 50
4 6 80
4 7 70
5 7 40
6 7 140
1 7
2 6
6 2
7 6 3
1 2 50
1 3 60
2 4 120
3 6 50
4 6 80
5 7 40
7 5
1 7
2 4
0 0 0

output

Case #1
80
60
60

Case #2
40
no path
80

思路

之前做过单源路径最小值最大的题, 用的dijkstra。

这里则是多源求路径最大值最小, 用floyd。 具体则是将原来floyd中 dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) 换成 dist[i][j] = min(dist[i][j], max(dist[i][k], dist[k][j]) 模板中 i→j 的总路径等于 i→k + k→j, 这里则是 i→j 的所有路径中最大权值 的最小值为 “i→k 和 k→j 的所有路径最大值的最小值” 的最大值

为什么需要用到max呢？ 因为如果用min的话, 得到的就不是i→k→j 这条路径中的最大权值, 也就无法得出结果。

代码

//------------------------------//
//          Made by Aze         //
//------------------------------//
/*
 *    problem:https://vjudge.csgrandeur.cn/contest/510867#problem/B
 *    date:8/17 3:23PM
 *
 */
 
//------- Include Area----------//
 
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
 
int readInt()
{
    int t;
    cin >> t;
    return t;
}
 
//------- Coding Area ---------//
 
const int N = 1e3 + 10, INF = 0x3f3f3f3f;
int n, m, q;
int dist[N][N];
 
void floyd()
{
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                dist[i][j] = min(dist[i][j], max(dist[i][k], dist[k][j]));
}
 
int main()
{
    cin.tie(0)->sync_with_stdio(false);
    int kase = 1;
    while (cin >> n >> m >> q && (n || m || q))
    {
        if (kase > 1)
            cout << "\n";
        cout << "Case #" << kase++ << endl;
        memset(dist, INF, sizeof dist);
        while (m--)
        {
            int a, b, c;
            cin >> a >> b >> c;
            dist[b][a] = dist[a][b] = min(dist[a][b], c);
        }
        floyd();
        while (q--)
        {
            int a, b;
            cin >> a >> b;
            if (dist[a][b] <= INF / 2)
                cout << dist[a][b] << endl;
            else
                cout << "no path\n";
        }
    }
}

反向链接