給定有向圖,每條邊有流量下界 low 和上界 up。求是否存在可行流,並輸出滿足條件的具體流量分配。
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、判斷、輸出
}
}
id 排序,確保順序正確。NO,否則 YES 後跟每條邊流量。