题目:

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

题目链接

裸网络流最大流模板题。
网络流基础知识及最大流求解思路:

数据结构与算法分析 - 网络流入门（Network Flow）

最大流求解Ford-Fulkerson算法详解:

7. 网络流算法–Ford-Fulkerson方法及其多种实现

AC代码:

// Ford-Fulkerson算法
#include 
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef unsigned long long ull;
typedef pair P;
const int INF = 0x3f3f3f3f;
const int maxn = 20;
const int mod = 1e9+7;
const double eps = 1e-8;
const double pi = asin(1.0)*2;
const double e = 2.718281828459;
void fre() {freopen("in.txt", "r", stdin);//freopen("out.txt", "w", stdout);
}int t;
int n, m;
int x, y, c;
// 起点、终点
int st, en;
// 增广路径流量
int flow;
// 最大流
int ans;
// 顶点标记数组
bool vis[maxn];
// 残留网
int maze[maxn][maxn];// DFS寻找增广路径
int dfs(int u, int FindFlow) {// 若找到汇点返回此增广路径中if (u == en) {return FindFlow;}// 若访问过此顶点则返回if (vis[u]) {return 0;}// 标记此顶点为已访问顶点vis[u] = 1;// 枚举寻找下一个顶点for (int i = 1; i <= n; ++i) {// 跳过两顶点之间容量为0的顶点if (maze[u][i]) {// 从i点寻找路径，并返回路径流量int LastLineFlow = dfs(i, FindFlow < maze[u][i] ? FindFlow : maze[u][i]);// 跳过路径流量为0的点if (LastLineFlow == 0) {continue;}// 找到增广路径后更新残留网maze[u][i] -= LastLineFlow;maze[i][u] += LastLineFlow;// 返回此增广路径流量return LastLineFlow;}}// 若未找到增广路径则返回0return 0;
}int main(){//fre();scanf("%d", &t);for (int Case = 1; Case <= t; ++Case) {mem(vis, 0);mem(maze, 0);scanf("%d%d", &n, &m);st = 1, en = n;while (m--) {scanf("%d%d%d", &x, &y, &c);// 这道题有重边所以写为+=,=会WAmaze[x][y] += c;}ans = 0;// 不断寻找增广路径while (flow = dfs(st, INF)) {// 增加流量ans += flow;mem(vis, 0);}printf("Case %d: %d\n", Case, ans);}return 0;
}

AC代码:

// Dinic算法
#include 
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef unsigned long long ull;
typedef pair P;
const int INF = 0x3f3f3f3f;
const int maxn = 2e3;
const int mod = 1e9+7;
const double eps = 1e-8;
const double pi = asin(1.0)*2;
const double e = 2.718281828459;
void fre() {freopen("in.txt", "r", stdin);//freopen("out.txt", "w", stdout);
}int t;
int n, m;
// 最大流结果
int ans;
// 起点终点
int st, en;
// 残留网
int c[maxn][maxn];
// 分层图深度
int depth[maxn];// bfs分层图
int DinicBfs() {queue que;mem(depth, -1);depth[st] = 0;que.push(st);while (!que.empty()) {int temp = que.front();que.pop();for (int i = 1; i <= n; ++i) {if (c[temp][i] && depth[i] < 0) {depth[i] = depth[temp] + 1;que.push(i);}}}if (depth[en] > 0) {return 1;}return 0;
}// dfs寻找增广路径
int DinicDfs(int point, int MaxFlow) {if (point == en) {return MaxFlow;}int FindFlow;for (int i = 1; i <= n; ++i) {if (c[point][i] && depth[i] == depth[point] + 1 && (FindFlow = DinicDfs(i, min(MaxFlow, c[point][i])))) {c[point][i] -= FindFlow;c[i][point] += FindFlow;return FindFlow;}}return 0;
}int main(){//fre();scanf("%d", &t);for (int Case = 1; Case <= t; ++Case) {mem(c, 0);scanf("%d%d", &n, &m);st = 1, en = n;int input_u, input_v, input_c;while (m--) {scanf("%d%d%d", &input_u, &input_v, &input_c);// 有重边所以一定要用"+="c[input_u][input_v] += input_c;}// Dinic主过程ans = 0;while (DinicBfs()) {ans += DinicDfs(st, INF);}// 输出结果printf("Case %d: %d\n", Case, ans);}return 0;
}