BZOJ 3504 [CQOI2014] 危橋 解題詳解：雙源雙匯最大流與流量可行性判定

問題描述

N 個島嶼（0~N-1），橋分為普通橋（無限通行）和危橋（最多通行 2 次）。Alice 需在 a1、a2 間往返 an 次，Bob 需在 b1、b2 間往返 bn 次。判斷是否存在滿足所有約束的路徑方案。N < 50，an, bn ≤ 50。

核心建模：網絡流轉化

關鍵洞察

• 往返一次 = 兩條單向路徑（a1→a2 和 a2→a1），總需求流量 = 2×an + 2×bn
• 危橋容量 = 2，普通橋容量 = INF
• 雙源雙匯問題：不能簡單疊加兩個獨立最大流，必須聯合建模

正確建模步驟

1. 建立超級源點 S 和超級匯點 T
2. S → a1 容量 an，S → a2 容量 an（Alice 兩個方向）
       S → b1 容量 bn，S → b2 容量 bn（Bob 兩個方向）
3. a1 → T 容量 an，a2 → T 容量 an
       b1 → T 容量 bn，b2 → T 容量 bn
4. 島嶼間邊：危橋容量 2，普通橋容量 INF（雙向各加一條）
5. 計算最大流，若等於總需求 2(an+bn) 則初步可行

關鍵修正：流向正確性驗證

上述模型可能出現「Alice 的流跑到了 Bob 的匯點」導致假陽性。解決方案：交換 Bob 的源匯點重跑一次（即 b1↔b2 互換），若兩次均滿流則真正可行。原理：若存在錯配流，交換後必會導致瓶頸使流量不足。

算法選擇：Dinic 最大流

• N ≤ 50，點數極小，Dinic O(E√V) 充分高效
• 邊數 ≤ N² ≈ 2500，雙向建圖後 ≈ 5000
• 需支持多測試用例，每次重置圖結構

代碼框架（關鍵部分）

// 邊結構
struct Edge { int to, cap, rev; };
vector G[MAXN];
int level[MAXN], iter[MAXN];

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

bool bfs(int s, int t) {
    memset(level, -1, sizeof(level));
    queue q; level[s] = 0; q.push(s);
    while (!q.empty()) {
        int v = q.front(); q.pop();
        for (auto &e : G[v])
            if (e.cap > 0 && level[e.to] < 0)
                level[e.to] = level[v] + 1, q.push(e.to);
    }
    return level[t] >= 0;
}

int dfs(int v, int t, int f) {
    if (v == t) return f;
    for (int &i = iter[v]; i < G[v].size(); i++) {
        Edge &e = G[v][i];
        if (e.cap > 0 && level[v] < level[e.to]) {
            int d = dfs(e.to, t, min(f, e.cap));
            if (d > 0) { e.cap -= d; G[e.to][e.rev].cap += d; return d; }
        }
    }
    return 0;
}

int max_flow(int s, int t) {
    int flow = 0, inf = 1e9;
    while (bfs(s, t)) {
        memset(iter, 0, sizeof(iter));
        int f;
        while ((f = dfs(s, t, inf)) > 0) flow += f;
    }
    return flow;
}

// 主邏輯
bool solve() {
    build_graph();           // 正常連接
    if (max_flow(S, T) != total_need) return false;
    swap(b1, b2);            // 交換 Bob 源匯
    clear_graph();
    build_graph();
    return max_flow(S, T) == total_need;
}

複雜度與優化

• 時間：O(2 × Dinic) ≈ O(E√V) 每測試用例，極快
• 空間：O(V + E) ≈ 數 KB
• 關鍵優化：鄰接表存儲、當前弧優化（iter 數組）、分層圖 BFS

總結

本題是「多源多匯最大流可行性判定」的經典變體。核心難點在於識別雙源雙匯不能獨立建模，必須聯合建圖並通過源匯交換驗證流向正確性。Dinic 算法模板熟練度直接決定編碼速度。