BZOJ 3931 [CQOI2015] 網絡吞吐量：最短路 + 最大流

問題描述

給定無向圖，節點為路由器（1 為源，n 為匯），邊有長度 d。每個路由器有吞吐量上限 c（源匯點無限大）。數據包**必須沿最短路徑**轉發。求從 1 到 n 的最大吞吐量。
約束：n ≤ 500，m ≤ 100,000，d, c ≤ 10^9。

解法思路：兩階段建圖

1. 跑最短路：從源點 1 跑 Dijkstra 得到 dis[i]（到各點最短距離）。
2. 構建分層網絡：
   • 每個原節點 i 拆為 i（入）和 i+n（出），連邊 i → i+n 容量 c[i]（節點容量限制）。
   • 對每條原邊 (u, v, d)：若 dis[v] == dis[u] + d，加邊 u+n → v 容量 INF；若 dis[u] == dis[v] + d，加邊 v+n → u 容量 INF。只保留最短路 DAG 上的邊。
3. 跑最大流：在構建的有向圖上從 s=1 到 t=2n 跑 Dinic，即為答案。

關鍵代碼片段

// Dijkstra 計算最短距離
priority_queue, vector>, greater>> q;
dis[1] = 0; q.push({0,1});
while (!q.empty()) {
    int u = q.top().second; q.pop();
    if (vis[u]) continue; vis[u] = true;
    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].to;
        if (dis[v] == -1 || dis[v] > dis[u] + e[i].v) {
            dis[v] = dis[u] + e[i].v;
            q.push({dis[v], v});
        }
    }
}

// 建流網絡
memset(head, 0, sizeof(head)); cnt = 1;
s = 1; t = 2*n;
for (int i = 1; i <= n; ++i) add_edge(i, i+n, c[i], 0); // 點容量
for (int i = 1; i <= m; ++i) {
    if (dis[y[i]] == dis[x[i]] + z[i]) add_edge(x[i]+n, y[i], INF, 0);
    if (dis[x[i]] == dis[y[i]] + z[i]) add_edge(y[i]+n, x[i], INF, 0);
}
dinic(); // 標準 Dinic 模板
printf("%lld\n", ans);

複雜度分析

• Dijkstra：O(m log n)。
• 最大流：節點 2n ≤ 1000，邊 O(m + n)，Dinic 實測極快。
• 總體滿足限制。

小結

經典「最短路約束下的最大流」模型：先用最短路篩選合法邊構建 DAG，再拆點轉化為標準最大流。代碼結構清晰，模板複用性強。