求大佬找错

P3376 【模板】网络最大流

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

\texttt{Dinic} 即可解决问题qwq


|