bellmanford @ 2019-08-11 12:22:16
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
#define OPTIMIZE ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define In inline
#define Re register
#define db double
#define ll long long
const int M=1e5+5;
int n,m,s,t,tot=0,ans=0,liu[M],pre[M],first[M];
bool vis[M];
struct Edge{
int nxt,to,val;
}e[M<<1];
int read(){
int x=0,y=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') y=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return x*y;
}
void add(int x,int y,int z){
tot++;
e[tot].nxt=first[x];
first[x]=tot;
e[tot].to=y;
e[tot].val=z;
}
bool bfs(){
queue<int> Q;
memset(vis,0,sizeof(vis));
Q.push(s);
vis[s]=1;
liu[s]=1<<30;
while(!Q.empty()){
int u=Q.front();
Q.pop();
for(int i=first[u];i;i=e[i].nxt){
int v=e[i].to,w=e[i].val;
if(!vis[v]&&w){
vis[v]=1;
pre[v]=i;
liu[v]=min(liu[u],w);
Q.push(v);
if(v==t) return 1;
}
}
}
return 0;
}
void EK(){
while(bfs()){
int u=t;
while(u!=s){
e[pre[u]].val-=liu[t];
e[pre[u]^1].val+=liu[t];
u=e[pre[u]^1].to;
}
ans+=liu[t];
}
}
int main(){
n=read(),m=read(),s=read(),t=read();
for(int i=1;i<=m;i++){
int x=read(),y=read(),z=read();
add(x,y,z);
add(y,x,0);
}
EK();
printf("%d\n",ans);
}
by bellmanford @ 2019-08-11 12:22:52
写错了
是死循环
by Kevin_Wa @ 2019-08-11 12:38:03
红名去你的刚学OI
by bellmanford @ 2019-08-11 12:38:38
才几个月也算是啦QwQ
by bellmanford @ 2019-08-11 12:39:57
QAQ没有人呐
by bellmanford @ 2019-08-11 12:41:04
窝才打卡11天就红了耶
by Happynewyear @ 2019-08-11 12:42:02
红名去你的刚学OI
by pjykk @ 2019-08-11 12:43:07
刚学OI就学EK的dalao
by 表白 @ 2019-08-11 12:43:37
我也刚学,请问你这是死循环了吗
by bellmanford @ 2019-08-11 12:44:07
@表白 嗯嗯嗯
by wkywkywky @ 2019-08-11 12:46:15
去你的刚学OI