UVA 1324 Bring Them There：時擴網絡最大流

問題模型

N（≤ 50）個星系，M 條雙向隧道，每天每條隧道只能通過一艘飛船。需從 S 運 K（≤ 50）台超算到 T，求最少天數及每日調度方案。

時擴網絡構建

• 第 d 天的星系 i 表示為節點 (d−1)×N + i。
• 「停留」邊：(d−1, i) → (d, i) 容量 INF。
• 「隧道」邊：(d−1, u) → (d, v) 和 (d−1, v) → (d, u) 容量 1。
• 源點 = (0, S)，匯點 = (D, T)（D 逐日增長直到流量 ≥ K）。

Dinic 最大流 + 方案重構

每日增加一層網絡，跑 Dinic 累積流量。達到 K 後停止。
方案重構：檢查每日隧道邊的流量（反向邊容量），按飛船編號分配輸出。

關鍵代碼片段

struct Dinic {
    struct Edge { int to, rev, cap; };
    vector<vector<Edge>> G;
    vector<int> level, it;
    void addEdge(int u, int v, int cap) { ... }
    bool bfs(int s, int t) { ... }
    int dfs(int u, int t, int f) { ... }
    int maxflow(int s, int t) { ... }
};
// 主循環
int day = 1, flow = 0;
while (flow < K) {
    // 添加第 day 層節點與邊
    flow += dinic.maxflow(S, T);
    if (flow >= K) break;
    ++day;
}
// 重構路徑：遍歷隧道邊的反向流量

複雜度

節點數 ≤ D×N，D ≤ K+直徑 ≤ 100，Dinic O(E√V) 極快。