题目描述

给定一个无向图，其中包含 $n$ 个节点。每对节点之间有一条边，边的容量用一个对称的 $n\times n$ 矩阵表示。对于每对节点 $(A,B)$，需要计算从节点 $A$ 到节点 $B$ 的最大流值。

输入格式：

• 第一行：测试用例数量 $N$
• 每个测试用例：
  • 第一行：节点数 $n$ ($0\le n\le 200$)
  • 接下来 $n$ 行：$n\times n$ 的容量矩阵

输出格式：

• 对于每个测试用例：
  • 输出 “Case #z:”，其中 $z$ 是测试用例编号
  • 接下来 $n$ 行，每行 $n$ 个整数，表示所有点对的最大流矩阵
  • 对角线元素必须为 $0$

题目分析

问题本质

这是一个所有点对最大流问题。在无向图中，对于每对节点 $(u,v)$，我们需要计算它们之间的最大流值。

直接方法的局限性

最直接的方法是对于每对节点 $(u,v)$ 都运行一次最大流算法（如 $\text{Dinic}$ 或 $\text{Edmonds-Karp}$）。然而，这种方法的时间复杂度为 $O(n^2\cdot T_{\text{maxflow}})$，其中 $T_{\text{maxflow}}$ 是单次最大流计算的时间复杂度。

对于 $n=200$，需要计算 $C_{200}^2=19900$ 次最大流，这在时间上是不可行的。

$\text{Gomory-Hu}$ 树的优势

$\text{Gomory-Hu}$ 树（也称为流等价树）是一个优雅的解决方案，它能够将 $n$ 个节点的无向图的所有点对最大流信息编码在一棵树中。关键性质是：

• 对于原图中的任意两个节点 $u$ 和 $v$，它们在原图中的最大流等于它们在 $\text{Gomory-Hu}$ 树中路径上的最小边权。

构建 $\text{Gomory-Hu}$ 树只需要进行 $n-1$ 次最大流计算，然后通过 $n$ 次 $\text{BFS}$ 或 $\text{DFS}$ 即可得到所有点对的最大流值。

算法复杂度

• $\text{Gomory-Hu}$ 树构建：$O(n\cdot T_{\text{maxflow}})$
• 所有点对查询：$O(n^2)$
• 总复杂度：$O(n\cdot T_{\text{maxflow}}+n^2)$

使用 $\text{Dinic}$ 算法时，$T_{\text{maxflow}}=O(V^{2}E)$，在稀疏图上表现良好。

解题思路

步骤 1：实现 $\text{Dinic}$ 最大流算法

$\text{Dinic}$ 算法是解决最大流问题的高效算法，包含以下组件：

1. 层次图构建：使用 $\text{BFS}$ 为每个节点分配层次
2. 阻塞流计算：使用 $\text{DFS}$ 在层次图中寻找增广路径
3. 迭代过程：重复上述步骤直到无法找到增广路径

步骤 2：实现 $\text{Gomory-Hu}$ 树构建

$\text{Gomory-Hu}$ 树的构建过程：

1. 初始化父节点数组 $\text{parent}$，所有节点的父节点初始为节点 $0$
2. 对于 $i=1$ 到 $n-1$：
   • 计算节点 $i$ 和 $\text{parent}[i]$ 之间的最大流 $f$
   • 在树中添加边 $(i,\text{parent}[i])$，权重为 $f$
   • 更新后续节点的父节点：如果节点 $j$ ($j>i$) 与 $i$ 在同一连通分量中，且当前父节点与 $i$ 相同，则更新 $\text{parent}[j]=i$

步骤 3：计算所有点对最大流

构建 $\text{Gomory-Hu}$ 树后，对于每个节点 $i$：

1. 执行 $\text{BFS}$ 从节点 $i$ 出发
2. 维护从 $i$ 到每个节点路径上的最小边权
3. 这个最小边权就是 $i$ 到该节点的最大流值

步骤 4：处理边界情况

• $n=0$：无输出
• $n=1$：输出单个 $0$
• $n\ge 2$：正常处理

代码实现

// All Pairs Maximum Flow
// UVa ID: 11594
// Verdict: Accepted
// Submission Date: 2025-11-12
// UVa Run Time: 0.140s
//
// 版权所有（C）2025，邱秋。metaphysis # yeah dot net

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#include <climits>

using namespace std;

struct Dinic {
    struct Edge {
        int to, rev;
        int cap, flow;
    };

    vector<vector<Edge>> graph;
    vector<int> level, ptr;
    int n;

    Dinic(int n) : n(n), graph(n), level(n), ptr(n) {}

    void addEdge(int from, int to, int cap) {
        graph[from].push_back({to, (int)graph[to].size(), cap, 0});
        graph[to].push_back({from, (int)graph[from].size() - 1, cap, 0});
    }

    bool bfs(int s, int t) {
        fill(level.begin(), level.end(), -1);
        queue<int> q;
        level[s] = 0;
        q.push(s);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (const Edge& e : graph[u]) {
                if (level[e.to] == -1 && e.flow < e.cap) {
                    level[e.to] = level[u] + 1;
                    q.push(e.to);
                }
            }
        }
        return level[t] != -1;
    }

    int dfs(int u, int t, int pushed) {
        if (u == t || pushed == 0) return pushed;
        for (int& cid = ptr[u]; cid < graph[u].size(); cid++) {
            Edge& e = graph[u][cid];
            if (level[e.to] == level[u] + 1 && e.flow < e.cap) {
                int tr = dfs(e.to, t, min(pushed, e.cap - e.flow));
                if (tr > 0) {
                    e.flow += tr;
                    graph[e.to][e.rev].flow -= tr;
                    return tr;
                }
            }
        }
        return 0;
    }

    int maxFlow(int s, int t) {
        for (auto& edges : graph) {
            for (Edge& e : edges) {
                e.flow = 0;
            }
        }
        int flow = 0;
        while (bfs(s, t)) {
            fill(ptr.begin(), ptr.end(), 0);
            while (int pushed = dfs(s, t, INT_MAX)) {
                flow += pushed;
            }
        }
        return flow;
    }
};

struct GomoryHuTree {
    int n;
    vector<vector<int>> tree;
    vector<vector<pair<int, int>>> adj;

    GomoryHuTree(int n) : n(n), tree(n, vector<int>(n, 0)), adj(n) {}

    void build(Dinic& dinic) {
        vector<int> parent(n, 0);
        for (int i = 1; i < n; i++) {
            int flow = dinic.maxFlow(i, parent[i]);
            
            // 更新树结构
            adj[i].emplace_back(parent[i], flow);
            adj[parent[i]].emplace_back(i, flow);
            
            // 更新后续节点的父节点
            for (int j = i + 1; j < n; j++) {
                if (dinic.level[j] != -1 && parent[j] == parent[i]) {
                    parent[j] = i;
                }
            }
        }
        
        // 使用BFS计算所有点对在树上的最小边权
        for (int i = 0; i < n; i++) {
            vector<int> minCapacity(n, INT_MAX);
            minCapacity[i] = INT_MAX; // 自己到自己的容量应该是无穷大，但题目要求对角线为0
            
            queue<int> q;
            q.push(i);
            vector<bool> visited(n, false);
            visited[i] = true;
            
            while (!q.empty()) {
                int u = q.front();
                q.pop();
                
                for (const auto& edge : adj[u]) {
                    int v = edge.first;
                    int cap = edge.second;
                    
                    if (!visited[v]) {
                        visited[v] = true;
                        // 路径上的最小容量是当前路径最小容量和当前边容量的较小值
                        minCapacity[v] = min(minCapacity[u], cap);
                        q.push(v);
                    }
                }
            }
            
            // 填充结果矩阵
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    tree[i][j] = 0; // 对角线为0
                } else {
                    tree[i][j] = minCapacity[j];
                }
            }
        }
    }
};

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

    int numCases;
    cin >> numCases;
    for (int caseIdx = 1; caseIdx <= numCases; caseIdx++) {
        int n;
        cin >> n;
        vector<vector<int>> capacity(n, vector<int>(n));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> capacity[i][j];
            }
        }

        cout << "Case #" << caseIdx << ":\n";
        if (n == 0) {
            continue;
        }
        if (n == 1) {
            cout << "0\n";
            continue;
        }

        Dinic dinic(n);
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (capacity[i][j] > 0) {
                    dinic.addEdge(i, j, capacity[i][j]);
                }
            }
        }

        GomoryHuTree gomoryHu(n);
        gomoryHu.build(dinic);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (j > 0) cout << " ";
                cout << gomoryHu.tree[i][j];
            }
            cout << "\n";
        }
    }

    return 0;
}

算法总结

$\text{Gomory-Hu}$ 树是解决所有点对最大流问题的经典方法，它将指数级别的问题转化为多项式级别。通过将原图转化为等价的树结构，我们能够高效地计算所有点对之间的最大流值。

这种方法的关键洞察是：无向图的最大流具有很好的结构性质，可以被编码在一棵树中。这种转化不仅减少了计算量，还提供了对网络流结构的深刻理解。

对于 $n\le 200$ 的规模，使用 $\text{Dinic}$ 算法构建 $\text{Gomory-Hu}$ 树是完全可行的，能够在合理时间内解决问题。