# Flow Problem（HDOJ 3549）

1. 1:Problem Description
2. 2:Input
3. 3:Output
4. 4:Sample Input
5. 5:Sample Output
6. 6:My Code

## 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. `

```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```

## My Code

``````#include <iostream>
#include <cstring>
#include <queue>
#define maxn 20
#define maxm 1005
#define inf 0x3f3f3f3f
using namespace std;
int T;
int n, m;
struct edge
{
int v;
int c;
int next;
} e[maxm << 1];
int tot;
int cnt;
int cur[maxn];
void add(int u, int v, int c)
{
e[++tot].v = v;
e[tot].c = c;
}
int dep[maxn];
bool bfs(int s, int t)
{
queue<int> q;
memset(dep, 0, sizeof(dep));
dep[s] = 1;
q.push(s);
for (int i = 1; i <= n; i++)
while (!q.empty())
{
s = q.front();
q.pop();
for (int i = head[s]; ~i; i = e[i].next)
if (e[i].c && !dep[e[i].v])
{
dep[e[i].v] = dep[s] + 1;
if (e[i].v == t)
return true;
q.push(e[i].v);
}
}
return false;
}
int dfs(int s, int t, int flow)
{
if (s == t || !flow)
return flow;
int ans = 0;
for (int &i = cur[s]; ~i; i = e[i].next)
if (e[i].c && dep[e[i].v] == dep[s] + 1)
{
int res = dfs(e[i].v, t, min(flow, e[i].c));
if (!res)
dep[e[i].v] = 0;
e[i].c -= res;
e[i ^ 1].c += res;
ans += res;
flow -= res;
if (!flow)
break;
}
return ans;
}
void init()
{
memset(e, -1, sizeof(e));
tot = -1;
}
int dinic(int s, int t)
{
int ans = 0;
while (bfs(s, t))
ans += dfs(s, t, inf);
return ans;
}
int main()
{
cin >> T;
while (T--)
{
init();
cin >> n >> m;
for (int i = 0; i < m; i++)
{
int u, v, c;
cin >> u >> v >> c;