# HDU3549 Flow Problem（最大流模板题）

## Flow Problem

• Time Limit: 5000/5000 MS (Java/Others)
• Memory Limit: 65535/32768 K (Java/Others)
• Total Submission(s): 20685
• Accepted Submission(s): 9706

### Problem Description

Network flow is a well-known difficult problem for ACMers. Given a graph, your task is to find out the maximum flow for the weighted directed graph.

### Input

The first line of input contains an integer T, denoting the number of test cases.
For each test case, the first line contains two integers N and M, denoting the number of vertexes and edges in the graph. (2 <= N <= 15, 0 <= M <= 1000)
Next M lines, each line contains three integers X, Y and C, there is an edge from X to Y and the capacity of it is C. (1 <= X, Y <= N, 1 <= C <= 1000)

### Output

For each test cases, you should output the maximum flow from source 1 to sink N.

### Sample Input

2
3 2
1 2 1
2 3 1
3 3
1 2 1
2 3 1
1 3 1 

### Sample Output

Case 1: 1
Case 2: 2 

### 链接

http://acm.hdu.edu.cn/showproblem.php?pid=3549

### 代码

• Dinic
StatusAccepted
Time109ms
Memory1928kB
Length2148
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int maxn = 110;

int n, m;
struct Edge
{
int u, v, cap;
Edge() {}
Edge(int u, int v, int cap): u(u), v(v), cap(cap) {}
}edge[maxn*maxn];

int R, S, T;
vector <int> E[maxn]; //边集
int dis[maxn];
int current[maxn];

void addedge(int u, int v, int cap)
{
E[u].push_back(R);
edge[R++] = Edge(u, v, cap); // 正向边
E[v].push_back(R);
edge[R++] = Edge(v, u, 0); // 方向边容量为0
// 正向边下标通过异或就得到反向边下标, 2 ^ 1 == 3 ; 3 ^ 1 == 2，R从0开始
}

int bfs()
{
memset(dis, 0x3f, sizeof(dis)); // 初始化为0x3f3f3f3f
queue <int> Q;
Q.push(S);
dis[S] = 0;
while (!Q.empty())
{
int u = Q.front();
Q.pop();
for (int i = 0; i < E[u].size(); ++i)
{
Edge &e = edge[E[u][i]];
if (e.cap > 0 && dis[e.v] == 0x3f3f3f3f)
{
dis[e.v] = dis[u] + 1;
Q.push(e.v);
}
}
}
return dis[T] < 0x3f3f3f3f; // 返回是否能够到达汇点
}

int dinic(int u, int maxflow)
{
if (u == T)
return maxflow;
for (int i = current[u]; i < E[u].size(); ++i) // 当前弧优化，保存u点增广到了第几条边
{
current[u] = i;
Edge &e = edge[E[u][i]];
if (dis[e.v] == dis[u] + 1 && e.cap > 0)
{
int flow = dinic(e.v, min(maxflow, e.cap));
if (flow)
{
e.cap -= flow; // 正向边流量减少
edge[E[u][i] ^ 1].cap += flow; // 方向边流量增加
return flow;
}
}
}
return 0;
}

int DINIC()
{
int ans = 0;
while (bfs())
{
int flow;
memset(current, 0, sizeof(current)); // bfs后清空当前弧数组
while (flow = dinic(S, 0x3f3f3f3f)) // 一次bfs可以进行多次增广
ans += flow;
}
return ans;
}

int main()
{
int t, u, v, cap, kase = 0;
scanf("%d", &t);
while (t--)
{
scanf("%d%d", &n, &m);
R = 0, S = 1, T = n; // 边序号，源点，汇点
for (int i = 0; i <= n; ++i)
E[i].clear();
memset(edge, 0, sizeof(edge));
for (int i = 0; i < m; ++i)
{
scanf("%d%d%d", &u, &v, &cap);
}
printf("Case %d: %d\n", ++kase, DINIC());
}
return 0;
}
• EK邻接表
tatusAccepted
Time1560ms
Memory13728kB
Length1921
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 1010;
const int inf = 0x3f3f3f3f;

struct Edge
{
int next, to, w;
}edge[maxn*maxn];
struct Node
{
int id, v;
}pre[maxn];
int n, m, cnt;
bool vis[maxn];

void init()
{
cnt = 0;
memset(edge, 0, sizeof(edge));
}

void addedge(int u, int v, int w)
{
edge[cnt].to = v;
edge[cnt].w = w;
}

bool bfs(int s, int t)
{
memset(pre, -1, sizeof(pre));
memset(vis, 0, sizeof(vis));
queue <int> Q;
Q.push(s);
vis[s] = true;
pre[s].v = s;
while (!Q.empty())
{
int u = Q.front();
Q.pop();
for (int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].to;
if (!vis[v] && edge[i].w > 0)
{
pre[v].v = u;
pre[v].id = i;
vis[v] = true;
if (v == t)
return true;
Q.push(v);
}
}
}
return false;
}

int EK(int s, int t)
{
int maxflow = 0;
while (bfs(s, t))
{
int _min = inf;
for (int i = t; i != s; i = pre[i].v)
_min = min(_min, edge[pre[i].id].w);
for (int i = t; i != s; i = pre[i].v)
{
edge[pre[i].id].w -= _min;
edge[pre[i].id ^ 1].w += _min;
}
maxflow += _min;
}
return maxflow;
}

int main()
{
int T, u, v, w, kase = 0;
scanf("%d", &T);
while (T--)
{
init();
scanf("%d%d", &n, &m);
for (int i = 0; i < m; ++i)
{
scanf("%d%d%d", &u, &v, &w);
}
printf("Case %d: %d\n", ++kase, EK(1, n));
}
return 0;
}
• EK邻接矩阵
StatusAccepted
Time546ms
Memory5748kB
Length1487
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 1010;
const int inf = 0x3f3f3f3f;

int G[maxn][maxn];
int n, m;
bool vis[maxn];
int pre[maxn];

bool bfs(int s, int t)
{
queue <int> Q;
memset(vis, 0, sizeof(vis));
memset(pre, -1, sizeof(pre));
Q.push(s);
vis[s] = true;
pre[s] = s;
while (!Q.empty())
{
int u = Q.front();
Q.pop();
for (int i = 1; i <= n; ++i)
{
if (G[u][i] > 0 && !vis[i])
{
pre[i] = u;
vis[i] = true;
if (i == t)
return true;
Q.push(i);
}
}
}
return false;
}

int EK(int s, int t)
{
int maxflow = 0;
while (bfs(s, t)) // 寻找增广路
{
int _min = inf;
for (int i = t; i != s; i = pre[i])
_min = min(_min, G[pre[i]][i]);
for (int i = t; i != s; i = pre[i])
{
G[pre[i]][i] -= _min;
G[i][pre[i]] += _min;
}
maxflow += _min;
}
return maxflow;
}

int main()
{
int T, u, v, w, kase = 0;
scanf("%d", &T);
while (T--)
{
scanf("%d%d", &n, &m);
memset(G, 0, sizeof(G));
for (int i = 0; i < m; ++i)
{
scanf("%d%d%d", &u, &v, &w);
G[u][v] += w;
}
printf("Case %d: %d\n", ++kase, EK(1, n));
}
return 0;
}

The end.
2018-07-22 星期日