带容量限制网络最优传输路径求解及算法咨询

本问题不采用网络最大流的经典定义。给定由n个泵站组成的网络，部分泵站间通过管道连接，每条管道有指定容量。
对于每对泵站u和v，需找出构成简单路径的最优管道集合，使u到v的输气量最大。输气量与路径上管道的最小容量成正比：若无路径输出0；若存在无容量限制的路径输出1000000009。

第一行输入整数n（1≤n≤500），为泵站数量。
接下来输入n×n的邻接矩阵g_{i,j}（-1≤g_{i,j}≤10^9）：g_{i,j}=0表示i与j间无管道；g_{i,j}=-1表示管道无容量限制；主对角线元素均为0。

输出n×n的矩阵ans_{u,v}，其中ans_{u,v}为u到v最优路径上的最小管道容量。若u=v或存在无容量限制路径，ans_{u,v}=1000000009；若无路径则输出0。

（保留原示例输入输出内容）

我尝试用Floyd-Warshall算法，但结果不对。以下是我的代码，求正确算法的实现思路或完整代码：

#include <iostream>
#include <vector>

using namespace std;

const int INF = 1e9 + 9;

int main() {
    int n;
    cin >> n;
    vector<vector<int>> inp(n, vector<int>(n));
    vector<vector<int>> res(n, vector<int>(n, INF));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> inp[i][j];
            if (i == j || inp[i][j] == -1) {
                res[i][j] = INF;
            }
            else if (inp[i][j] > 0) {
                res[i][j] = inp[i][j];
            }
        }
    }
    for (int u = 0; u < n; u++) {
        for (int v = 0; v < n; v++) {
            if (u != v && inp[u][v] == 0) {
                for (int k = u + 1; k < v; k++) {
                    res[u][v] = min(res[u][v], max(res[u][k], res[k][v]));
                }
            }
        }
    }
    for (auto& x : res) {
        for (int i : x) {
            if (i == INF) {
                cout << 1000000009 << " ";
            }
            else {
                cout << i << " ";
            }
        }
        cout << endl;
    }
    return 0;
}

这是典型的最大瓶颈路径问题，同时需要优先处理包含无容量限制管道的路径（这类路径结果直接为1e9+9）。

你的代码错误点 #

1. Floyd循环顺序错误：正确的Floyd-Warshall算法需要先遍历中间节点k，再遍历起点i和终点j，你的循环顺序无法覆盖所有可能的路径更新。
2. 更新公式错误：最大瓶颈路径需要取路径中最小边的最大值，正确公式应为res[i][j] = max(res[i][j], min(res[i][k], res[k][j]))，你使用的min(..., max(...))逻辑完全相反。
3. 无容量路径处理缺失：未考虑通过中间节点形成的无容量限制路径，比如i到k存在无容量管道，k到j有有效路径时，i到j应标记为无容量限制。
4. 初始值错误：你将无管道的情况初始化为INF，这会导致后续判断混乱，无管道应初始化为0表示无路径。

正确实现代码 #

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const long long INF = 1e9 + 9;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<vector<long long>> res(n, vector<long long>(n, 0));

    // 初始化结果矩阵
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            long long val;
            cin >> val;
            if (i == j) {
                res[i][j] = INF;
            } else if (val == -1) {
                res[i][j] = INF;
            } else if (val > 0) {
                res[i][j] = val;
            } else {
                res[i][j] = 0; // 无管道初始化为0
            }
        }
    }

    // Floyd-Warshall变种，处理最大瓶颈和无容量路径
    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                // 若中间路径存在无容量限制管道，直接标记为INF
                if (res[i][k] == INF || res[k][j] == INF) {
                    if (res[i][j] != INF) {
                        res[i][j] = INF;
                    }
                } 
                // 若i到k、k到j都有有效路径，更新最大瓶颈
                else if (res[i][k] > 0 && res[k][j] > 0) {
                    long long current_bottleneck = min(res[i][k], res[k][j]);
                    if (current_bottleneck > res[i][j]) {
                        res[i][j] = current_bottleneck;
                    }
                }
            }
        }
    }

    // 输出结果
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (res[i][j] == INF) {
                cout << INF << " ";
            } else if (res[i][j] == 0 && i != j) {
                cout << 0 << " ";
            } else {
                cout << res[i][j] << " ";
            }
        }
        cout << "\n";
    }

    return 0;
}

核心逻辑说明 #

1. 初始化：区分自身节点、无容量管道、有容量管道、无管道四种情况，分别赋值。
2. Floyd更新：
   • 优先处理无容量路径：只要路径中存在无容量管道，直接标记结果为INF。
   • 最大瓶颈计算：对于有效路径，取通过中间节点的路径的最小边，与当前结果取最大值，确保得到最优路径的最小容量。
3. 输出处理：将INF转换为题目要求的1e9+9，无路径的情况输出0。

内容的提问来源于stack exchange，提问作者imnic