# HDU-3549 网络流
## [HDU-3549](http://acm.hdu.edu.cn/showproblem.php?pid=3549)
## 分析
没啥分析的, 最大流模板题(结果自己写WA了)
果然网络流还是得硬套模板
注意这道题有重边, 需要叠加和判断流量.
## 代码(EK)
```cpp
// -------------- GLOBAL ----------------
int n, m;
int x, y, c;
int cap[25][25], flow[25][25]; // 容量和流量
// -------------- FUNC ----------------
int bfs() {
LL res = 0;
queue<int> que;
while (1) {
int book[25] = {0}; // 1-v的最小残量, 同时用作标记
int p[25] = {0}; // 关键位置, 用来标记父元素便于回溯
book[1] = INF;
que.push(1);
while (!que.empty()) {
int u = que.front();
que.pop();
F1(v, n) {
if (!book[v] && cap[u][v] > flow[u][v]) {
p[v] = u;
book[v] = min(book[u], cap[u][v] - flow[u][v]);
que.push(v);
}
}
}
if (!book[n])
break;
// 开始更新
for (int x = n; x != 1; x = p[x]) {
flow[p[x]][x] += book[n];
flow[x][p[x]] -= book[n];
}
res += book[n];
}
return res;
}
// -------------- MAIN ----------------
int main() {
int T;
scanf("%d", &T);
for (int t = 1; t <= T; ++t) {
scanf("%d%d", &n, &m);
fill0(cap);
fill0(flow);
F1(i, m) {
scanf("%d%d%d", &x, &y, &c);
cap[x][y] += c; // 处理重边
}
printf("Case %d: %lld\n", t, bfs());
}
return 0;
}
```
![]()