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

题目链接

裸网络流最大流模板题。
网络流基础知识及最大流求解思路:数据结构与算法分析 - 网络流入门（Network Flow）
最大流求解Ford-Fulkerson算法详解:7. 网络流算法–Ford-Fulkerson方法及其多种实现

AC代码:

// Ford-Fulkerson算法
#include <bits/stdc++.h>
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<int,int> 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;
        }
    }
    // 若未找到增广路径则返回0
    return 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);
            // 这道题有重边所以写为+=,=会WA
            maze[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 <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
#define XDebug(x) cout<<#x<<"="<<x<<endl;
#define ArrayDebug(x,i) cout<<#x<<"["<<i<<"]="<<x[i]<<endl;
#define print(x) out(x);putchar('\n')
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
typedef pair<ll,ll> PLL;
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;
template <class T>
inline bool read(T &ret) {
    char c;
    int sgn;
    if (c = getchar(), c == EOF) {
        return false;
    }
    while (c != '-' && (c < '0' || c > '9')) {
        c = getchar();
    }
    sgn = (c == '-') ? -1 : 1;
    ret = (c == '-') ? 0 : (c - '0');
    while (c = getchar(), c >= '0' && c <= '9') {
        ret = ret * 10 + (c - '0');
    }
    ret *= sgn;
    return true;
}
template <class T>
inline void out(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) {
        out(x / 10);
    }
    putchar(x % 10 + '0');
}

int T;
// N:顶点数，E:边数
int N, E;
int X, Y, C;
// 分层数组
int Depth[maxn];
// 邻接矩阵
int Adj[maxn][maxn];

// Bfs搜索分层图，Start:起点，End:终点
bool Bfs(int Start, int End) {
    std::queue<int> Que;
    memset(Depth, -1, sizeof(Depth));
    Depth[Start] = 0;
    Que.push(Start);
    while (!Que.empty()) {
        int Vertex = Que.front();
        Que.pop();
        for (int i = 1; i <= N; ++i) {
            if (Depth[i] == -1 && Adj[Vertex][i]) {
                // 分层编号
                Depth[i] = Depth[Vertex] + 1;
                Que.push(i);
            }
        }
    }
    return Depth[End] > 0;
}

// Dfs搜索增广路径，Vertex:当前搜索顶点，End:终点，NowFlow:当前最大流量
int Dfs(int Vertex, int End, int NowFlow) {
    // 搜索到终点结束
    if (Vertex == End) {
        return NowFlow;
    }
    int FindFlow = 0;
    // 枚举顶点
    for (int i = 1; i <= N; ++i) {
        if (Adj[Vertex][i] && Depth[i] == Depth[Vertex] + 1) {
            FindFlow = Dfs(i, End, std::min(NowFlow, Adj[Vertex][i]));
            if (FindFlow) {
                // 找到增广路径后更新邻接矩阵残留网
                Adj[Vertex][i] -= FindFlow;
                Adj[i][Vertex] += FindFlow;
                // 返回搜索结果
                return FindFlow;
            }
        }
    }
    // 炸点优化
    if (!FindFlow) {
        Depth[Vertex] = -2;
    }
    // 未找到增广路径
    return false;
}

// Dinic算法，Start:起点，End:终点
int Dinic(int Start, int End) {
    // MaxFlow:最大流
    int MaxFlow = 0;
    // 分层搜索增广路径直至终点无法分层
    while (Bfs(Start, End)) {
        MaxFlow += Dfs(Start, End, INF);
    }
    // 返回结果
    return MaxFlow;
}

int main(int argc, char *argv[]) {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    read(T);
    for (int Case = 1; Case <= T; ++Case) {
        mem(Adj, 0);
        read(N); read(E);
        for (int i = 1; i <= E; ++i) {
            read(X); read(Y); read(C);
            Adj[X][Y] += C;
        }
        printf("Case %d: %d\n", Case, Dinic(1, N));
    }
#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    system("gedit out.txt");
#endif
    return 0;
}