Flow Problem
Time Limit: 5000/5000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 9735 Accepted Submission(s): 4562
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
第一道最大流，dinic算法：
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <vector>
#define MAXN 100+10
#define MAXM 2000+10
#define INF 10000000+10
using namespace std;
struct Edge
{
int from, to, cap, flow, next;
}edge[MAXM];
int n, m;
int dist[MAXN];//距离起点的距离
int top, head[MAXN], vis[MAXN];
int cur[MAXN];//cur[i]表示i点正在考虑的边 优化不再考虑已经用过的点 初始化为head
void init()
{
top = 0;
memset(head, -1, sizeof(head));
}
void addedge(int a, int b, int c)
{
Edge E1 = {a, b, c, 0, head[a]};
edge[top] = E1;
head[a] = top++;
Edge E2 = {b, a, 0, 0, head[b]};
edge[top] = E2;
head[b] = top++;
}
void getmap()
{
int a, b, c;
while(m--)
{
scanf("%d%d%d", &a, &b, &c);
addedge(a, b, c);
}
}
bool BFS(int start, int end)
{
//从残余网络找一条从start->end的路径(就是最短路的代码,每条边的边权为最大流量-当前流量,当这条边满流时最大流量=当前流量，边权为0）
//显然当找不到这样的路径时说明不能继续增加流量 则返回false 算法结束
int i;
memset(dist, -1, sizeof(dist));
memset(vis, 0, sizeof(vis));
queue<int> Q;
while(!Q.empty()) Q.pop();
Q.push(start);
vis[start] = 1;
dist[start] = 0;
while(!Q.empty())
{
int u = Q.front();
Q.pop();
for(i = head[u]; i != -1; i = edge[i].next)
{
Edge E = edge[i];
if(!vis[E.to] && E.cap > E.flow)
{
vis[E.to] = 1;
dist[E.to] = dist[u] + 1;
if(E.to == end) return true;
Q.push(E.to);
}
}
}
return false;
}
int DFS(int x, int a, int end)//增广路径 叠加当前start->end路径上的最小残量 a
{
if(x == end || a == 0) return a;
int flow = 0, f;
for(int& i = cur[x]; i != -1; i = edge[i].next)//从上次考虑的弧
{
Edge& E = edge[i];
if(dist[x]+1 == dist[E.to] && (f = DFS(E.to, min(a, E.cap-E.flow), end)) > 0)
{
E.flow += f;
edge[i^1].flow -= f;
flow += f;
a -= f;
if(a == 0) break;
}
}
return flow;
}
int Maxflow(int start, int end)
{
int flow = 0;
while(BFS(start, end))//找到1到n的最短路径
{
memcpy(cur, head, sizeof(head));
flow += DFS(start, INF, end);
}
return flow;
}
int main()
{
int t;
int k = 1;
scanf("%d", &t);
while(t--)
{
scanf("%d%d", &n, &m);
init();
getmap();
printf("Case %d: %d\n", k++, Maxflow(1, n));
}
return 0;
}