CUGB图论专题：排水系统中的最大流问题-EK与Dinic算法解析

### 问题描述
每当下雨时，约翰的农场中会形成一个覆盖贝茜最喜欢的苜蓿地的水塘。为了确保苜蓿地不被水淹没，约翰设计了一套复杂的排水系统，将水引导至附近的溪流。每条排水沟都有一个调节器，可以控制水流速度。给定每个排水沟的最大流量及整个系统的布局，我们需要确定从水源点到溪流的最大排水速率。

#### 输入格式
输入包含多组测试用例。每组测试用例的第一行包含两个整数N和M (0 <= N <= 200, 2 <= M <= 200)，分别表示排水沟的数量和交叉点的数量。交叉点1为水源点，交叉点M为溪流。接下来N行每行包含三个整数Si、Ei和Ci (1 <= Si, Ei <= M, 0 <= Ci <= 10,000,000)，表示一条从Si流向Ei的排水沟及其最大流量Ci。

#### 输出格式
对于每组测试用例，输出一行一个整数，表示从水源点到溪流的最大排水速率。

#### 示例
- **输入**
```plaintext
5 4
1 2 40
1 4 20
2 4 20
2 3 30
3 4 10
```
- **输出**
```plaintext
50
```

### 解法分析
此题属于经典的最大流问题，直接应用EK或Dinic算法即可解决。

#### EK算法
EK算法基于广度优先搜索（BFS）寻找增广路径，并在找到后调整流量。具体实现如下：
```cpp
#include
#include
using namespace std;
typedef long long ll;
const int MAXN = 205;
int n, m, pre[MAXN], vis[MAXN], Map[MAXN][MAXN];
ll ans;
bool bfs() {
memset(vis, 0, sizeof(vis));
queue q;
q.push(1);
vis[1] = 1;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v = 1; v <= m; ++v) {
if (!vis[v] && Map[u][v]) {
pre[v] = u;
if (v == m) return true;
q.push(v);
vis[v] = 1;
}
}
}
return false;
}
void augment() {
ll flow = LLONG_MAX;
for (int i = m; i != 1; i = pre[i])
flow = min(flow, (ll)Map[pre[i]][i]);
for (int i = m; i != 1; i = pre[i]) {
Map[pre[i]][i] -= flow;
Map[i][pre[i]] += flow;
}
ans += flow;
}
int main() {
while (cin >> n >> m) {
memset(Map, 0, sizeof(Map));
ans = 0;
for (int i = 0; i int u, v, w;
cin >> u >> v >> w;
Map[u][v] += w;
}
while (bfs()) augment();
cout < }
return 0;
}
```

#### Dinic算法
Dinic算法引入了分层图的概念，利用深度优先搜索（DFS）进一步优化性能。核心思想是通过BFS构建层次图，再用DFS寻找最短路径上的最小流量并更新。代码如下：
```cpp
#include
#include
using namespace std;
typedef long long ll;
const int MAXN = 205;
int n, m, d[MAXN], Map[MAXN][MAXN];
ll ans;
bool bfs() {
memset(d, -1, sizeof(d));
queue q;
q.push(1);
d[1] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v = 1; v <= m; ++v) {
if (d[v] == -1 && Map[u][v]) {
d[v] = d[u] + 1;
q.push(v);
}
}
}
return d[m] != -1;
}
ll dfs(int u, ll flow) {
if (u == m) return flow;
ll sum = 0;
for (int v = 1; v <= m; ++v) {
if (Map[u][v] && d[v] == d[u] + 1) {
ll f = dfs(v, min(flow, (ll)Map[u][v]));
if (f > 0) {
Map[u][v] -= f;
Map[v][u] += f;
sum += f;
flow -= f;
if (!flow) break;
}
}
}
return sum;
}
void dinic() {
while (bfs()) {
while (ll flow = dfs(1, LLONG_MAX))
ans += flow;
}
cout <}
int main() {
while (cin >> n >> m) {
memset(Map, 0, sizeof(Map));
ans = 0;
for (int i = 0; i int u, v, w;
cin >> u >> v >> w;
Map[u][v] += w;
}
dinic();
}
return 0;
}
```