Fujishige_Flow

fujishige.cpp

#include<cassert>
#include<queue>
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)
#define eprintf(s...)  fprintf(stderr, s)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }

// Fujishige
struct Flow {
    struct Edge {
	int src, dst;
	LL cap;
	int rev;
    };
    typedef vector<vector<Edge> > Graph;
    int N;
    Graph G;
    Flow(int N_) : N(N_), G(N) { }
    void add_edge(int x, int y, LL c) {
	G[x].push_back((Edge){ x, y, c, (int)G[y].size() });
	G[y].push_back((Edge){ y, x, c, (int)G[x].size()-1 });
    }
    LL _flow;
    LL flow(int source, int sink) {
	_flow = 0;
	LL A = 1LL<<30;
	VI v(N, N), r(N, N+1); vector<LL> b(N, 0); int i=0;
	v[0] = source; r[source] = 0;
	VI bb(N, 0); int bbi = 0;
	VI X;
	bool init = false;
	while (true) {
	    if (init) {
		REP (j, i+1) {
		    assert(v[j] < N);
		    r[v[j]] = N+1;
		    v[j] = N;
		}
		EACH (e, X) {
		    r[*e] = N+1;
		}
//		v.assign(N, N); r.assign(N, N+1);
		bbi++; //b.assign(N, 0);
		i = 0;
		v[0] = source; r[source] = 0;
		X.clear();
		init = false;
	    }
	    EACH (e, G[v[i]]) if (r[e->dst] > i) {
		if (bb[e->dst] < bbi) {
		    b[e->dst] = 0;
		    bb[e->dst] = bbi;
		}
		b[e->dst] += e->cap;
		if (b[e->dst] >= A && r[e->dst] == N+1) {
		    X.push_back(e->dst); r[e->dst] = N;
		    if (e->dst == sink) break;
		}
	    }
	    if (X.empty()) {
		A /= 2;
		if (A == 0) return _flow;
		else {
		    init = true;
		    continue;
		}
	    }
	    i++;
	    v[i] = X.back(); r[X.back()] = i; X.pop_back();
	    if (v[i] != sink) continue;
	    bbi++;
	    b[sink] = A; bb[sink] = bbi;
	    _flow += A;
	    for (int j=i; j>0; j--) {
		if (bb[v[j]] < bbi) {
		    b[v[j]] = 0;
		    bb[v[j]] = bbi;
		}
		EACH (e, G[v[j]]) if (r[e->dst] < j) {
		    LL f = min(b[v[j]], G[e->dst][e->rev].cap);
		    e->cap += f; G[e->dst][e->rev].cap -= f;
		    if (bb[e->dst] < bbi) {
			b[e->dst] = 0;
			bb[e->dst] = bbi;
		    }
		    b[v[j]] -= f; b[e->dst] += f;
		}
	    }
	    init = true;
	}
    }
};

int main() {
    int N, M;
    scanf("%d%d", &N, &M);
    Flow X(N);
    REP (i, M) {
	int a, b, c;
	scanf("%d%d%d", &a, &b, &c);
	X.add_edge(a-1, b-1, c);
    }

    printf("%lld\n", X.flow(0, N-1));

    return 0;
}