在網路流問題中，判斷哪些邊的容量增加能夠提升整體最大流量是一個經典且實用的課題。POJ 3204 正是圍繞這一核心問題展開：給定一個網路，找出所有若增加容量便能增大最大流值的邊。
顯而易見，只有在最大流計算後處於「滿流」狀態的邊，才可能成為關鍵邊。更進一步，若某條滿流邊是某條從源點到匯點路徑上唯一的滿流邊，那麼僅增加該邊容量便能打開新的增廣路徑，從而提升總流量。
標準做法是在跑完一次最大流（如 Dinic）後，得到殘余網路。接著進行兩次深度優先搜索：
S 出發，只走容量 > 0 的邊（非滿流邊），標記所有可達頂點；T 出發，在反向圖上同樣只走容量 > 0 的邊，標記所有可達頂點。若某條原圖滿流邊 (u, v) 滿足：u 被源點標記、v 被匯點標記，則說明存在一條「源點 → u」的非滿流路徑與一條「v → 匯點」的非滿流路徑，中間僅缺這條滿流邊。故該邊為關鍵邊，計數器 Num++。
作者採用更直觀的策略：對每條滿流邊，在殘余網路中臨時增加 1 單位容量，隨即從源點發起 BFS，若能到達匯點，說明確實出現了新增廣路，該邊即為關鍵邊。雖需多次 BFS，但結合陣列模擬佇列的高效 Dinic 實現，仍能在時限內通過。
struct Edge { int to, cap, next, from; } e[2000005];
int head[1005], dep[1005], q[2000005], tot = 1;
void addEdge(int u, int v, int c) {
e[++tot] = {v, c, head[u], u}; head[u] = tot;
e[++tot] = {u, 0, head[v], v}; head[v] = tot;
}
bool bfs(int s, int t) {
memset(dep, -1, sizeof(dep));
int hh = 0, tt = 0; q[tt++] = s; dep[s] = 0;
while (hh < tt) {
int u = q[hh++];
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].to;
if (e[i].cap && dep[v] == -1) {
dep[v] = dep[u] + 1;
if (v == t) return true;
q[tt++] = v;
}
}
}
return false;
}
int dfs(int u, int t, int f) {
if (u == t) return f;
int flow = 0;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].to, c = e[i].cap;
if (!c || dep[v] != dep[u] + 1) continue;
int pushed = dfs(v, t, min(c, f - flow));
e[i].cap -= pushed; e[i^1].cap += pushed;
flow += pushed;
if (flow == f) break;
}
if (!flow) dep[u] = 0;
return flow;
}
int dinic(int s, int t) {
int ans = 0;
while (bfs(s, t)) ans += dfs(s, t, INT_MAX);
return ans;
}
void solve() {
dinic(1, n);
int cnt = 0;
for (int i = 2; i <= tot; i += 2) { // 遍歷原圖邊（正向邊索引為偶數）
if (e[i].cap == 0) { // 滿流邊
e[i].cap = 1; // 臨時加 1 容量
if (bfs(1, n)) cnt++;
e[i].cap = 0; // 還原
}
}
printf("%d\n", cnt);
}
std::queue 開銷，BFS/DFS 速度顯著提升。i=2,4,6…），反向邊為 i^1，便於快速定位原圖邊。本題展示了最大流「關鍵邊」判定的兩大經典思路：雙向 DFS 標記法理論優雅、一次遍歷搞定；加流驗證法思路直觀、工程落地簡單。配合高效 Dinic 實現，均可輕鬆解決 POJ 3204。理解殘余網路中「非滿流路徑」與「滿流邊」的拓撲關係，是攻克此類問題的關鍵。
