Uva 567 进来复习Floyd算法模板

一、题意

每组数据有20个城市，给出每个城市与之相邻的城市，距离为1，不相邻的城市认为不可达。然后有q个询问，每次询问任意两个城市之间的距离。

二、解析

由于要询问任意两个城市之间的距离，因此这是一个多源最短路问题，即需要得到每两个点之间的最短路。这样的问题只能使用Floyd算法。算法复杂度为O(n^3)，在数据量小的时候非常方便。

PS: 这题的输入搞得相当复杂orz....我主要是想复习一下Floyd的模板而已....

三、代码

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
const int n = 20, INF = 1 << 29;
int kase = 1, q, d[n + 1][n + 1];

bool read(istream& in) {
    for(int i = 1; i <= n; i ++) {  // 初始化d
        for(int j = 1; j <= n; j ++) d[i][j] = INF;
        d[i][i] = 0;
    }
    for(int u = 1, m, v; u < n; u ++) {
        if(!(in >> m)) return 0;
        while(m --) in >> v, d[u][v] = d[v][u] = 1;
    }
    return 1;
}

void Floyd() {
    for(int k = 1; k <= n; k ++) {  // 枚举中间点
        for(int i = 1; i <= n; i ++) {
            for(int j = 1; j <= n; j ++) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
}

int main() {
    while(read(cin)) {
        Floyd();
        cin >> q;
        cout << "Test Set #" << kase ++ << "\n";
        while(q --) {
            int u, v;
            cin >> u >> v;
            cout << setw(2) << u << " to " << setw(2) << v << ": " << d[u][v] << "\n";
        }
        cout << endl;
    }
}

四、归纳

• Floyd算法用于处理多源最短路问题，正权负权均可处理，需要使用邻接矩阵来存放点距，大致模板如下：

const int INF = 1 << 29;
int n, d[maxn][maxn];

void init() {
    for(int i = 1; i <= n; i ++) {  // 初始化d
        for(int j = 1; j <= n; j ++) d[i][j] = INF;
        d[i][i] = 0;
    }
}

void Floyd() {
    for(int k = 1; k <= n; k ++) {  // 枚举中间点
        for(int i = 1; i <= n; i ++) {
            for(int j = 1; j <= n; j ++) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
}

int main() {
    ......
    init();
    Floyd();
    ......
}

• 要注意Floyd中会有INF相加的情况，因此INF值不能太大，这里取的是1<<29.