C++11(clang++ 3.9) 解法, 执行用时: 129ms, 内存消耗: 7684K, 提交时间: 2020-09-30 20:21:02

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=2e4+5,M=2e5+5,Inf=1e9;
struct Graph{int u,v,w;}gra[M];
struct Edge{int to,f,nxt;}e[M<<1];
int n,m,fst[N],tote,lev[N],nf[N],s,t,l,ans;
void adde(int u,int v,int f){e[++tote]=(Edge){v,f,fst[u]};fst[u]=tote;}
bool bfs(){
	queue<int>que;
	memset(lev,-1,sizeof(lev));
	que.push(s);lev[s]=0;
	while(!que.empty()){
		int u=que.front();que.pop();
		for(int i=fst[u],v;~i;i=e[i].nxt)if(e[i].f&&lev[v=e[i].to]<0)
			lev[v]=lev[u]+1,que.push(v);
	}
	return lev[t]>=0;
}
int dfs(int u,int lim){
	if(u==t)return lim;
	int flow=0;
	for(int i=nf[u],v,f,tmp;~i;i=e[i].nxt){
		v=e[i].to;f=e[i].f;
		if(f&&lev[v]==lev[u]+1){
			tmp=dfs(v,min(lim,f));
			e[i].f-=tmp;e[i^1].f=tmp;lim-=tmp;flow+=tmp;
			if(!lim){nf[u]=i;return flow;}
		}
	}
	nf[u]=-1;return flow;
}
void init(){memset(fst,-1,sizeof(fst));tote=1;}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)scanf("%d%d%d",&gra[i].u,&gra[i].v,&gra[i].w);
	scanf("%d%d%d",&s,&t,&l);init();
	for(int i=1;i<=m;i++)if(gra[i].w<l)adde(gra[i].u,gra[i].v,1),adde(gra[i].v,gra[i].u,1);
	while(bfs()){
		for(int i=1;i<=n;i++)nf[i]=fst[i];
		ans+=dfs(s,Inf);
	}
	init();
	for(int i=1;i<=m;i++)if(gra[i].w>l)adde(gra[i].u,gra[i].v,1),adde(gra[i].v,gra[i].u,1);
	while(bfs()){
		for(int i=1;i<=n;i++)nf[i]=fst[i];
		ans+=dfs(s,Inf);
	}
	printf("%d\n",ans);
	return 0;
}