Lates @ 2020-03-15 15:45:57
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define _min(a,b) ((a)<(b)?(a):(b))
#define int long long
using namespace std;
inline int read(){
register int x=0,f=0,ch=getchar();
while('0'>ch||ch>'9')f^=ch=='-',ch=getchar();
while('0'<=ch&&ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=getchar();
return f?-x:x;
}
const int MAX=100005,INF=0x3f3f3f3f;
queue<int>q;
struct E{
int e,next,w;
}e[MAX<<1];
int cnt=1,head[MAX];
inline void add(int u,int v,int w){
e[cnt]=(E){v,head[u],w};
head[u]=cnt++;
}
int res,ans,n,m,x,flow[MAX],pre[MAX],pr[MAX];
inline int bfs(int s,int t){
while(!q.empty())q.pop();
memset(pre,-1,sizeof(pre));
memset(pr,0,sizeof(pr));
pre[s]=0;
q.push(s);flow[s]=INF;
while(!q.empty()){
x=q.front();
q.pop();
if(x==t)break;
for(register int i=head[x];i;i=e[i].next){
if(e[i].w>0&&pre[e[i].e]==-1){
pre[e[i].e]=x;
pr[e[i].e]=i;
flow[e[i].e]=_min(flow[x],e[i].w);
q.push(e[i].e);
}
}
}
return pre[t]==-1?-1:flow[t];
}
inline void EK(int s,int t){
res=0;
while((res=bfs(s,t))!=-1){
x=t;ans+=res;
while(x!=s){
e[pr[x]].w-=res;
e[pr[x]+1].w+=res;
x=pre[x];
}
}
}
int u,v,w,S,T;
signed main(){
n=read(),m=read();S=read(),T=read();
for(register int i=1;i<=m;++i){
u=read(),v=read(),w=read();
add(u,v,w);add(v,u,0);
}
EK(S,T);
printf("%lld\n",ans);
return 0;
}
by Sol1 @ 2020-03-15 15:46:16
@Lates EK本来就能过(
by Lates @ 2020-03-15 15:46:57
@ClCN 复杂度不是
by Sol1 @ 2020-03-15 15:47:29
@Lates 但是一般不会到那个上界吧(
或者是您常数小 Orz
by StudyingFather @ 2020-03-15 15:48:06
网络流模板仅用来测板子正确性(
by __gcd @ 2020-03-15 15:48:25
@Lates 照你这么算Dinic好像也会炸掉
by Lates @ 2020-03-15 15:49:50
@ClCN @StudyingFather @一只大头 谢谢
by LTb_ @ 2020-03-15 16:11:35
因为你谷数据弱(
可以交到LOJ上看看qwq
by Lates @ 2020-03-15 17:53:43
@LTb_ loj EK+邻接矩阵都过了