Infiltrator @ 2019-05-24 21:06:37
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
#define N 10050
#define M 100050
#define INF 9999999
int n,m,s,t,num,head[N],maxflow,maxx[N],pre[N],last[N];
struct edge
{
int next,to,flow;
}tu[M*2];
void addedge(int u,int v,int w)
{
tu[++num]=(edge){head[u],v,w};
head[u]=num;
}
int bfs()
{
memset(maxx,0,sizeof(maxx));
queue<int> q;
q.push(s);maxx[s]=INF;
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=head[u];i;i=tu[i].next)
{
int v=tu[i].to,w=tu[i].flow;
if(maxx[v] || !w)continue;
maxx[v]=min(maxx[u],w);
pre[v]=u;last[v]=i;
if(v==t)return 1;
q.push(v);
}
}
return 0;
}
void change()
{
int now=t;
maxflow+=maxx[t];
while(now!=s)
{
tu[last[now]].flow-=maxx[t];
tu[last[now]^1].flow+=maxx[t];
now=pre[now];
}
}
int main()
{
scanf("%d%d%d%d",&n,&m,&s,&t);
int u,v,w;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&w);
addedge(u,v,w);
addedge(v,u,0);
}
while(bfs())
{cout<<maxx[t]<<endl;change();}
printf("%d",maxflow);
return 0;
}
by Lone_Star @ 2019-05-24 21:07:45
@坐山客 这是什么算法啊
by Lone_Star @ 2019-05-24 21:08:03
感觉不像dinic qwq
by Infiltrator @ 2019-05-24 21:15:55
@Flamire EK wtcl
by VenusM1nT @ 2019-05-24 21:38:25
写