Cptraser @ 2018-01-11 16:08:40
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
char tc()
{
static char fl[100000],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
int read()
{
char c;while(c=tc(),(c<'0'||c>'9')&&c!='-');
int x=0,y=1;c=='-'?y=-1:x=c-'0';
while(c=tc(),c>='0'&&c<='9')x=x*10+c-'0';
return x*y;
}
const int MAXN=10005,MAXM=100005;
int N,M,S,T,x,y,c,ans;
int W[MAXM],To[MAXM],cnt;
int l[MAXM*5],h,t,dist[MAXN];
vector <int> a[MAXN];
bool BFS()
{
h=t=0;
l[++t]=S;
memset(dist,0,sizeof(dist));dist[S]=1;
while(h<t){
int front=l[++h];
for(int i=0;i<a[front].size();i++){
int to=a[front][i];
if(!dist[To[to]] && W[to]>0){
dist[To[to]]=dist[front]+1;
l[++t]=To[to];
}
}
}
return dist[T]>0;
}
int find(int now,int x)
{
if(now==T) return x;
for(int i=0;i<a[now].size();i++){
int to=a[now][i];
if(dist[To[to]]==(dist[now]+1) && W[to]>0){
int fd=find(To[to],min(x,W[to]));
if(fd>0){
W[to]-=fd;
W[to^1]+=fd;
return fd;
}
}
}
return 0;
}
int main()
{
freopen("x.txt","r",stdin);
N=read(),M=read(),S=read(),T=read();
for(int i=1;i<=M;i++){
x=read(),y=read(),c=read();
W[cnt]=c,To[cnt]=y;a[x].push_back(cnt);cnt++;
W[cnt]=0,To[cnt]=x;a[y].push_back(cnt);cnt++;
}
while(BFS()){
ans+=find(S,2e9);
}
printf("%d",ans);
return 0;
}
by 韵城小管家 @ 2018-01-11 16:28:52
要建回边所以1e5大概不够,要2e5
by Cptraser @ 2018-01-14 14:29:52
谢谢
by 出言不逊王子 @ 2020-06-26 13:11:28
kg