首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式碼之家 >> 編程語言 >  >> C語言 >> C++ >> 關於C++

ZOJ 2314 Reactor Cooling:有上下界的網絡最大流

     編輯:關於C++

問題模型

給定有向圖,每條邊有流量下界 low 和上界 up。求是否存在可行流,並輸出滿足條件的具體流量分配。

標準轉化:上下界可行流 → 普通最大流

  1. 對每條邊 u→v,容量設為 up − low。
  2. 計算每個節點的「需求」 d[v] = Σ入邊 low − Σ出邊 low。
  3. 建立超級源 SS 和超級匯 TT:
     d[v] > 0 連 SS→v 容量 d[v];
     d[v] < 0 連 v→TT 容量 −d[v]。
  4. 在原圖中加一條 T→S 容量 INF 的邊(若有指定源匯)。
  5. 跑最大流,若 SS 出邊全部滿流則可行。

關鍵代碼片段

struct Edge { int to, rev, cap; };
vector<vector<Edge>> G;
void addEdge(int u, int v, int cap) {
    G[u].push_back({v, (int)G[v].size(), cap});
    G[v].push_back({u, (int)G[u].size() - 1, 0});
}
// Dinic
bool bfs(int s, int t) { ... }
int dfs(int u, int t, int f) { ... }
int maxflow(int s, int t) { ... }

輸出邊流量

原始邊 i 的實際流量 = low[i] + (原容量 − 剩餘容量)。需按輸入順序輸出,故保存邊的索引並排序。

完整代碼結構

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 205, MAXM = 20005, INF = 1e9;
struct Edge { int to, rev, cap; };
vector<Edge> G[MAXN];
int level[MAXN], iter[MAXN];
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) { ... }
struct OriginalEdge { int u, v, low, up, id; } E[MAXM];
int demand[MAXN];
int main() {
    int n, m; while (cin >> n >> m) {
        // 讀入、建圖、轉化、Dinic、判斷、輸出
    }
}

注意事項

  • 節點數 n ≤ 200,邊數 m ≤ 20000,Dinic O(E√V) 完全足夠。
  • 輸出時需將邊按 id 排序,確保順序正確。
  • 若無可行流輸出 NO,否則 YES 後跟每條邊流量。
  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式碼之家 All Rights Reserved