ZOJ 2314 帶上下界的網絡流可行流判斷 - 超級源匯構建法

問題建模

給定 n 個節點、m 條有向邊，每條邊有流量下界 low 和上界 high。無指定源匯點，要求滿足流量守恆（每點流入=流出）且所有邊流量在 [low, high] 內。判斷是否存在可行流，存在則輸出每條邊具體流量。

核心轉化：下界轉必經流量

1. 對每條邊 u→v [low, high]，拆分為：
   • 容量 high - low 的邊 u→v（可調節部分）
   • 強制流量 low：從超級源 S 向 v 連容量 low 的邊；從 u 向超級匯 T 連容量 low 的邊。
2. 在原網絡中加一條 T→S 容量 INF 的邊，將「有源匯可行流」轉化為「無源匯循環流」。
3. 跑最大流 S→T，若所有 S 出邊、T 入邊均滿流 → 存在可行流。

流量還原公式

原邊 u→v 實際流量 = low + (原容量 - 剩餘容量) = high - 剩餘容量。
代碼中記錄每條邊在圖中的索引，跑完流後直接讀取反向邊容量即為已用流量。

關鍵代碼片段 (Dinic)

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

void addEdge(int u, int v, int c) {
    G[u].push_back({v, c, (int)G[v].size()});
    G[v].push_back({u, 0, (int)G[u].size()-1});
}

bool bfs(int s) { /* 分層圖構建 */ }
int dfs(int v, int t, int f) { /* 多路增廣 */ }
int maxFlow(int s, int t) { /* Dinic 主循環 */ }

完整流程

int main() {
    while (cin >> n >> m) {
        init();
        // 1. 讀入邊，建立上述轉化圖，記錄原邊索引
        // 2. maxFlow(S, T) == 總下界和 ? "可行" : "不可行"
        // 3. 若可行，再跑一次 maxFlow(original_S, original_T) 最大化流量（可選）
        // 4. 按輸入順序輸出每條邊流量
    }
}

常見坑點

• 多測試用例：每輪必須 clear() 圖、重置陣列。
• 下界 > 上界：直接判無解。
• 長整型：流量和可能超 int，用 long long。
• 邊索引記錄：用結構體存 u, v, idx_in_G 便於最後取流量。

複雜度

Dinic O(E√V) 對於典型規模（V≤200, E≤1000）極快。若圖密集可考慮 ISAP 或 HLPP。