BZOJ_2561.cpp

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int MAXN=20000+10;
const int MAXM=400000+10;
const int inf=100000000;

struct node {
	int v, flow;
	int next;
}E[MAXM];

int from[MAXM], to[MAXM], weight[MAXM];
int head[MAXN], level[MAXN], que[MAXN];
int S, T, N, M, L, cnt;

void addedge(int u, int v, int a, int b) {
	E[cnt].v=v; E[cnt].flow=a; E[cnt].next=head[u]; head[u]=cnt++;
	E[cnt].v=u; E[cnt].flow=b; E[cnt].next=head[v]; head[v]=cnt++;
}

bool dinic_bfs() {
	for (int i=0; i<=N; i++) level[i]=-1;
	que[0]=S; level[S]=0;
	for (int h=0, t=1; h<t; h++) {
		int u=que[h], v;
		for (int now=head[u]; now!=-1; now=E[now].next)
			if (level[v=E[now].v]==-1&&E[now].flow>0) {
				level[v]=level[u]+1;
				que[t++]=v;
			}
	}
	return (level[T]!=-1);
}

int dinic_dfs(int u, int low) {
	if (u==T) return low;
	int ret=0, tmp, v;
	for (int now=head[u]; now!=-1&&ret<low; now=E[now].next) {
		if (level[v=E[now].v]==level[u]+1&&E[now].flow>0) {
			if (tmp=dinic_dfs(v, min(E[now].flow, low-ret))) {
				E[now].flow-=tmp; E[now^1].flow+=tmp; ret+=tmp;
			}
		}
	}
	if (!ret) level[u]=-1;
	return ret;
}

int dinic() {
	int maxflow=0, t;
	while (dinic_bfs()) {
		while (t=dinic_dfs(S, inf)) maxflow+=t;
	}
	return maxflow;
}

void init() {
	cnt=0;
	for (int i=0; i<=N; i++) head[i]=-1;
}

int main() {
	scanf("%d%d", &N, &M);
	for (int i=0; i<M; i++) scanf("%d%d%d", from+i, to+i, weight+i);
	scanf("%d%d%d", &S, &T, &L);
	init();
	for (int i=0; i<M; i++)
		if (weight[i]<L) addedge(from[i], to[i], 1, 1);
	int ret=dinic();
	init();
	for (int i=0; i<M; i++)
		if (weight[i]>L) addedge(from[i], to[i], 1, 1);
	ret+=dinic();
	printf("%d\n", ret);
	return 0;
}