uva 820（最大流）

最大流的裸题，直接贴了模板。

#include <cstdio>
#include <iostream>
#include <sstream>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;
#define ll long long
#define _cle(m, a) memset(m, a, sizeof(m))
#define repu(i, a, b) for(int i = a; i < b; i++)
#define repd(i, a, b) for(int i = b; i >= a; i--)
#define sfi(n) scanf("%d", &n)
#define pfi(n) printf("%d
", n)
#define sfi2(n, m) scanf("%d%d", &n, &m)
#define pfi2(n, m) printf("%d %d
", n, m)
#define pfi3(a, b, c) printf("%d %d %d
", a, b, c)
#define maxn 101
const int inf = 0x3f3f3f3f;
struct SAP
{
    int cap[maxn][maxn], flow[maxn][maxn];///容量,流量
    int n;    ///顶点数
    int h[maxn], vh[maxn], source, sink;
    ///某个点到sink点的最短距离，h[i]的计数, source点, sink点
    void init(int n)
    {
        this->n = n;
        memset(cap, 0, sizeof(cap));
    }
    void addCap(int i, int j, int val)
    {
        cap[i][j] += val;
    }
    /**
        参数: 节点编号，和该节点能用的最大流量
        返回: 此次找到的最大流量
    */
    int sap(const int idx, const int maxCap)
    {
        if(idx == sink)
            return maxCap;///最后一个结点。。。
        int l = maxCap, d, minH = n;
///此次的残余流量, 某次使用的流量, 邻居的最小流量
        for(int i = 0; i < n; i ++)
        {
            if(cap[idx][i]-flow[idx][i] > 0)
            {
                if(h[idx]==h[i]+1)
                {
                    d = sap(i, min(l, cap[idx][i]-flow[idx][i]));
///下次找到的流量
                    flow[idx][i] += d;             ///更新边的残余流量
                    flow[i][idx] -= d;
                    l -= d;                         ///更新本次参与流量
                    if(h[source]==n||l==0) return maxCap-l;///GAP
                }
                minH=min(minH, h[i]+1);            ///更新h[idx]
            }
        }
        if(l == maxCap)                          ///not found!
        {
            vh[h[idx]] --;                        ///GAP
            vh[minH] ++;
            if(vh[h[idx]] == 0)
                h[source] = n;
            h[idx] = minH;
        }
        return maxCap - l;
    }
    int solve(int source, int sink)
    {
        if(source == sink)    return inf;
        this->sink = sink;
        this->source = source;
        memset(flow, 0, sizeof(flow));
        memset(h, 0, sizeof(h));
        memset(vh, 0, sizeof(vh));
        int ans = 0;
        while(h[source] != n)
            ans += sap(source, inf);
        return ans;
    }
}sap;

int main()
{
    int s, t, c, n, x, y, w, kase = 0;
    while(sfi(n) && n)
    {
        kase++;
        sap.init(n);
        sfi2(s, t), sfi(c);
        s--, t--;
        repu(i, 0, c)
        {
            sfi2(x, y), sfi(w);
            x--, y--;
            sap.addCap(x, y, w);
            sap.addCap(y, x, w);
        }
        printf("Network %d
", kase);
        printf("The bandwidth is %d.

", sap.solve(s, t));
    }
    return 0;
}