3493441984zz @ 2018-11-27 21:05:07
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#define inf 0x3f3f3f3f
using namespace std;
struct Edge
{
int to,nxt,dis;
}edge[100010];
int head[10010],cur[10010],deep[10010];
int n,m,s,t,ans,cnt=-1;
void add(int from,int to,int dis,int flag)
{
edge[++cnt].to=to;
edge[cnt].nxt=head[from];
head[from]=cnt;
if(flag)
edge[cnt].dis=dis;
}
bool bfs()
{
memset(deep,0x7f,sizeof(deep));
for(int i=1;i<=n;++i)
cur[i]=head[i];
queue<int> dui;
dui.push(s);
deep[s]=0;
while(!dui.empty())
{
int now=dui.front();
dui.pop();
for(int i=head[now];i!=-1;i=edge[i].nxt)
{
if(deep[edge[i].to]>inf&&edge[i].dis)
{
deep[edge[i].to]=deep[now]+1;
dui.push(edge[i].to);
}
}
}
if(deep[t]<inf)
return 1;
return 0;
}
int dfs(int now,int limit)
{
if(!limit||now==t)
return limit;
int flow=0,f;
for(int i=cur[now];i!=-1;i=edge[i].nxt)
{
cur[now]=i;
if(deep[now]+1==deep[edge[i].to]&&(f=dfs(edge[i].to,min(limit,edge[i].dis))))
{
flow+=f;
limit-=f;
edge[i].dis-=f;
edge[i^1].dis+=f;
if(!limit)
break;
}
}
return flow;
}
void dinic()
{
while(bfs())
ans+=dfs(s,inf);
}
int main()
{
memset(head,-1,sizeof(head));
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i=1;i<=m;++i)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w,1);
add(v,u,0,0);
}
dinic();
printf("%d",ans);
return 0;
}
by y2823774827y @ 2018-11-27 21:20:46
@野心qwq %%%dalao
by y2823774827y @ 2018-11-27 21:21:08
@野心qwq M<=100000,数组开小了
by 3493441984zz @ 2018-11-28 19:59:10
@y2823774827y 哈哈哈,哪里比得上你,真的是
by 3493441984zz @ 2018-11-28 20:00:22
@y2823774827y 可是我还是RE了qwq
by 3493441984zz @ 2018-11-28 20:01:13
@y2823774827y 大佬帮忙找找错误呗
by 3493441984zz @ 2018-11-28 20:04:03
@y2823774827y AC了,开了1000000才AC是什么鬼。。。
by y2823774827y @ 2018-11-28 20:44:18
@野心qwq 双向边开200010过了
by 3493441984zz @ 2018-11-28 20:51:30
@y2823774827y 哦哦,不记得要双向边。。。