POJ 2396 帶源匯上下界網絡流可行流判斷 - 超級源匯+滿流檢查

問題建模

n 行 m 列矩陣，給定每行和、每列和，以及若干約束（如「所有元素 > 1」、「第 1 行第 2 列 = 5」）。判斷是否存在滿足所有約束的矩陣。

網絡流轉化

1. 源點 S → 每行節點 Rᵢ，容量 = 行和。
2. 每列節點 Cⱼ → 匯點 T，容量 = 列和。
3. Rᵢ → Cⱼ 容量 = [low, high]，由約束推導：
   • 「> d」 → low = d+1, high = INF
   • 「= d」 → low = high = d
   • 「< d」 → low = 0, high = d-1
   • 無約束 → [0, INF]
4. 檢查約束衝突：若某邊 low > high → 直接無解。

有源匯上下界可行流判斷標準流程

1. 構建上述圖，記錄每條 Rᵢ→Cⱼ 邊的索引。
2. 引入超級源 SS、超級匯 TT：
   • 原邊 u→v [low, cap] → 容量 cap-low 的邊 u→v。
   • SS→v 容量 low；u→TT 容量 low。
3. 加 T→S 容量 INF 邊，將有源匯轉無源匯循環流。
4. 跑 SS→TT 最大流，若所有 SS 出邊、TT 入邊均滿流 → 存在可行流。
5. 關鍵步驟：刪除 T→S 邊，在原圖 S→T 再跑一次最大流，得到最大可行流（題目僅需判斷可行性，此步可省略）。

約束處理技巧

// 約束類型：0 0  全體
//            0 c  第 c 列
//            r 0  第 r 行
//            r c  單元格 (r,c)
void applyConstraint(int r, int c, char op, int d) {
    auto update = [&](int u, int v, int low, int high) {
        L[u][v] = max(L[u][v], low);
        R[u][v] = min(R[u][v], high);
        if (L[u][v] > R[u][v]) flag = true; // 衝突
    };
    if (r == 0 && c == 0)      // 全體
        for (i=1..n) for (j=1..m) update(i, j+n, ...);
    else if (r == 0)           // 整列
        for (i=1..n) update(i, c+n, ...);
    else if (c == 0)           // 整行
        for (j=1..m) update(r, j+n, ...);
    else                       // 單元格
        update(r, c+n, ...);
}

複雜度與工程細節

• 節點數 ≤ 260，邊數 ≤ 10000，Dinic/ISAP 極快。
• 多測試用例：每輪 clear() 圖、重置 L/R 矩陣。
• 用 int 足夠（行列和 ≤ 10⁴），但累加和建議 long long。