POJ1273【网络流】

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;
const int maxnE = 1e6 + 7;
const int maxn  = 1e5 + 7;
const int maxnQ = 1e6 + 7;
const int inf   = 0x3f3f3f3f;

struct edge {
    int v;///弧尾
    int cap;///容量
    int nxt;///指向下一条从同一个弧头出发的弧
}e[maxnE];

int head[maxn],cnt;
int d[maxn],cur[maxn],pre[maxn],num[maxn];
int source,sink;///超级源、超级汇
int nv;///编号修改的上限
int n,m;

queue <int> q;

void add(int u, int v, int capacity) {
    e[cnt].v = v;
    e[cnt].cap = capacity;
    e[cnt].nxt = head[u];
    head[u] = cnt++;
    //正向边

    e[cnt].v = u;
    e[cnt].cap = 0;
    e[cnt].nxt = head[v];
    head[v] = cnt++;
    //反向边
}

void rev_bfs() {///反向bfs
    memset(num, 0, sizeof(num));
    memset(d, -1, sizeof(d));
    d[sink] = 0;///超级汇直接标记
    num[0] = 1;
    q.push(sink);
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(int i = head[u]; ~i; i = e[i].nxt) {
            int v = e[i].v;
            if(~d[v]) continue;///已经标过号
            d[v] = d[u] + 1;
            q.push(v);
            num[d[v]]++;
        }
    }
}

int ISAP() {
    memcpy(cur, head, sizeof(cur));///当前弧优化
    rev_bfs();
    int flow = 0, u = pre[source] = source;
    int i;
    while(d[sink] < nv) {///最长的一条链上，最大的下标是nv-1，如果大于等于nv说明已断层
        //printf("flow:%d\n",flow);
        if(u == sink) {///如果找到一条增广路，则沿着此条路修改flow
            int f = inf, neck;
            for(i = source; i != sink; i = e[cur[i]].v) {///修改流量
                if(f > e[cur[i]].cap) {
                    f = e[cur[i]].cap;///不断减少所需要的流量
                    neck = i;///记录回退点，不用回到起点再找
                }
            }
            for(i = source; i != sink; i = e[cur[i]].v) {///修改流量
                e[cur[i]].cap -= f;
                e[cur[i] ^ 1].cap += f;
            }
            flow += f;
            u = neck;///回退
        }
        for(i = cur[u]; ~i; i = e[i].nxt) {
            if(d[e[i].v] + 1 == d[u] && e[i].cap) break;
        }
        if(~i) {
            //如果存在可行的增广路
            cur[u] = i;
            pre[e[i].v] = u;
            u = e[i].v;
        } else {///否则回退，重新找增广路
            if(0 == (--num[d[u]])) break;
            int mind = nv;
            for(i = head[u]; ~i; i = e[i].nxt) {
                if(e[i].cap && mind > d[e[i].v]) {///寻找可以增广的最小下标
                    cur[u] = i;
                    mind = d[e[i].v];
                }
            }
            d[u] = mind + 1;
            num[d[u]]++;
            u = pre[u];///回退
        }
    }
    return flow;
}

void init() {///初始化
    memset(head, -1, sizeof(head));
    cnt = 0;
}

void solve()
{
    int u,v,c;
    init();
    for(int i = 0; i < m; ++i) {
        scanf("%d %d %d",&u, &v, &c);
        add(u,v,c);
    }
    source = 1, sink = n, nv = sink + 1;
    printf("%d\n",ISAP());
}

int main()
{
    while(scanf("%d %d", &m, &n) != EOF) {
        solve();
    }
    return 0;
}