求助

P3376 【模板】网络最大流

ethan0328 @ 2023-08-15 17:03:44

我的网络流板子能过这题,但是比正常的板子慢将近10倍,自己测了一下发现增广的次数要多将近5,6倍,求帮调。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=210,M=5e3+10;
struct edge
{
    int to,next,mx;
};
int n,m,ind=1,head[N];
edge e[M*2];
int now[N],pos[N];
queue<int> q;
void add(int x,int y,int z)
{
    e[++ind].to=y;
    e[ind].mx=z;
    e[ind].next=head[x];
    head[x]=ind;
}
bool bfs(int s,int t)
{
    int x;
    memset(pos,0,sizeof(pos));
    while(!q.empty())
    {
        q.pop();
    }
    q.push(s);
    pos[s]=1;
    while(!q.empty())
    {
        x=q.front();
        q.pop();
        for(int i=head[x];i;i=e[i].next)
        {
            if(e[i].mx&&!pos[e[i].to])
            {
                pos[e[i].to]=pos[x]+1;
                q.push(e[i].to);
                if(e[i].to==t)
                {
                    return 1;
                }
            }
        }
    }
    return 0;
}
int dfs(int x,int flow,int t)
{
    if(x==t)
    {
        return flow;
    }
    int rest=flow,p,y;
    for(;now[x]&&rest;now[x]=e[now[x]].next)
    {
        p=now[x];
        if(e[p].mx&&pos[e[p].to]==pos[x]+1)
        {
            y=dfs(e[p].to,min(e[p].mx,rest),t);
            if(!y)
            {
                pos[e[p].to]=0;
            }
            e[p].mx-=y;
            e[p^1].mx+=y;
            rest-=y;
        }
    }
    return flow-rest;
}
int dinic(int s,int t)
{
    int ret=0,x;
    while(bfs(s,t))
    {
        for(int i=1;i<=n;i++)
        {
            now[i]=head[i];
        }
        while(true)
        {
            x=dfs(s,2e9,t);
            if(!x)
            {
                break;
            }
            ret+=x;
        }
    }
    return ret;
}
signed main()
{
    int x,y,z,s,t;
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y>>z;
        add(x,y,z);
        add(y,x,0);
    }
    cout<<dinic(s,t);
}

by Argvchs @ 2023-08-15 17:24:08

啊不对这里确实错了,不然 now 要多改一次

if ((rest -= y) == 0) break;

by ethan0328 @ 2023-08-15 18:25:23

@Argvchs thx


|