网络流模板-JZTXT

#include <cstdio>
#include <cstring>
#include <stack>
#include <queue>
#include <cassert>
#include <list>
#include <vector>
#define sd std::
#define UP(i,s,e) for(auto i=s; i<e; ++i)
constexpr int INF = 0x3f3f3f3f;
constexpr int N = 1200, M = 120000;
namespace m{ // }{{{
using ll = long long;
int in, im, is, it;
struct Edge{
	int nxt;
	int to;
	int lf; // left flow
} edges[M*2+2];
int height[N]; ll ex[N];
int head[N], gap[N+1];
sd stack<int> hnods[N]; // height == x nods: hnods[x]
int maxhei = 0; // overflow_maxhei

void addedge(int s, int t, int c){
	static int cnt = 2;
	edges[cnt] = {head[s], t, c};
	edges[cnt^1] = {head[t], s, 0};
	head[s] = cnt;
	head[t] = cnt^1;
	cnt += 2;
}

void relabel(int x){
	height[x] = in;
	for(int i=head[x]; i; i=edges[i].nxt){
		if(edges[i].lf) height[x] = sd min(height[x], height[edges[i].to]);
	}
	if(++height[x] < in){
		hnods[height[x]].push(x);
		maxhei = sd max(maxhei, height[x]);
		++gap[height[x]];
	}
}

void push(int x){
	for(int i=head[x]; i; i=edges[i].nxt){
		int t = edges[i].to, w = edges[i].lf;
		if(w == 0) continue;
		if(height[t]!=height[x]-1 && x != is){ continue; }
		int df = x == is ? w : (int)sd min(ex[x], (ll)w);
		edges[i].lf -= df;
		edges[i^1].lf += df;
		ex[x] -= df;
		if(ex[t] == 0 && t != it && t != is){
		   	hnods[height[t]].push(t);
			maxhei = sd max(maxhei, height[t]);
		}
		ex[t] += df;
		if(ex[x] == 0) return;
	}
}

int gethiest(){
	while(hnods[maxhei].empty() && maxhei >= 0) maxhei--;
	if(maxhei == -1) return -1;
	int ret = hnods[maxhei].top();
	hnods[maxhei].pop();
	return ret;
}

void bfs_init(){
	memset(height, 0x3f, sizeof height);
	height[it] = 0;
	sd queue<int> todo;
	todo.push(it);
	while(!todo.empty()){
		int s = todo.front();
		todo.pop();
		for(int i=head[s]; i; i=edges[i].nxt){
			int t = edges[i].to;
			if(edges[i^1].lf && height[t] > height[s] + 1){
				height[t] = height[s] + 1;
				todo.push(t);
			}
		}
	}
}

void hlpp(){
	bfs_init();
	// memset gap 0
	if(height[is] == INF) return;
	else height[is] = in;
	UP(i, 0, in){
		if(height[i] != INF) gap[height[i]]++;
	}
	push(is);
	int x;
	while((x = gethiest()) != -1){
		push(x);
		if(ex[x]){
			if(!--gap[height[x]]){
				UP(i, 0, in){
					if(i == is || i == it) continue;
					if(height[i] > height[x] && height[i] < in+1)
						height[i] = in+1;
				}
			}
			relabel(x);
		}
	}
	return;
}

void work(){
	scanf("%d%d%d%d", &in, &im, &is, &it);
	is--; it--;
	UP(i, 0, im){
		int iu, iv, ic;
		scanf("%d%d%d", &iu, &iv, &ic);
		iu--; iv--;
		addedge(iu, iv, ic);
	}
	hlpp();
	printf("%lld\n", ex[it]);
}
} // }}}
int main(){m::work(); return 0;}