[hdu1532]最大流

裸最大流，求最大流一般步骤如下：

（1）所有正向边权初始化为容量，反向边权初始化为0

（2）找增广路

（3）找到则进入（4），否则得到最大流并退出

（4）增广路上所有边减去最小边权，相应的方向边加上最小边权，然后返回（2）

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <ctime>
#include <deque>
#include <queue>
using namespace std;
 
struct MaxFlow {
private:
    const static int maxn = 2e2 + 7;
    struct Edge {
        int u, v, w;
        Edge(int u = 0, int v = 0, int w = 0): u(u), v(v), w(w) {}
    };
    vector<vector<int> > G;
    vector<Edge> E;
    int S, T, maxflow;
    bool vis[maxn];
    int Q[maxn], fa[maxn], Y[maxn], head, tail, flow[maxn];
 
public:
    void init(int s, int t, int n) {
        G.clear();
        G.resize(n + 2);
        E.clear();
        S = s;
        T = t;
        maxflow = 0;
    }
    void add(int u, int v, int w) {
        E.push_back(Edge(u, v, w));
        E.push_back(Edge(v, u, 0));
        int sz = E.size();
        G[u].push_back(sz - 2);
        G[v].push_back(sz - 1);
    }
    bool bfs(int src) {
        head = tail = 0;
        memset(vis, 0, sizeof(vis));
        Q[tail ++] = src;
        flow[0] = 0x7fffffff;
        vis[src] = true;
        while (head < tail) {
            int node = Q[head ++];
            if (node == T) {
                maxflow += flow[head - 1];
                int p = head - 1;
                while (p) {
                    E[Y[p]].w -= flow[head - 1];
                    E[Y[p] ^ 1].w += flow[head - 1];
                    p = fa[p];
                }
                return true;
            }
            for (int i = 0; i < G[node].size(); i ++) {
                int e = G[node][i];
                if (!vis[E[e].v] && E[e].w) {
                    vis[E[e].v] = true;
                    fa[tail] = head - 1;
                    Y[tail] = e;
                    flow[tail] = min(flow[head - 1], E[e].w);
                    Q[tail ++] = E[e].v;
                }
            }
        }
        return false;
    }
    int solve() {
        while (bfs(S));
        return maxflow;
    }
} ;
MaxFlow solver;
 
int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif // ONLINE_JUDGE
    int n, m;
    while (cin >> m >> n) {
        solver.init(1, n, n);
        for (int i = 0; i < m; i ++) {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            solver.add(u, v, w);
        }
        cout << solver.solve() << endl;
    }
    return 0;
}