蒟蒻求助,网络流板子(Dinic) 91points #9 TLE

P3376 【模板】网络最大流

无尽星空 @ 2020-08-10 16:15:53

#include<bits/stdc++.h>
#define LL long long
#define R register int
using namespace std;
const int N=205,M=10005;
int n,m,h[N],to[M],nx[M],cnt=1,now[N],d[N],s,t;
LL flow[M],ans,inf=10000000000;
queue<int> q;
void add(int x,int y,int fl) {to[++cnt]=y;flow[cnt]=fl;nx[cnt]=h[x];h[x]=cnt;} 
inline int read()
{
    int s=0;char c=getchar();
    while(!isdigit(c))  c=getchar();
    while(isdigit(c))  s=(s<<3)+(s<<1)+(c^48),c=getchar();
    return s;
}
bool bfs()
{
    int x;
    for(x=1;x<=n;x++)  d[x]=0,now[x]=h[x];
    while(q.size())  q.pop();
    q.push(s);d[s]=1;
    while(q.size())
    {
        x=q.front();q.pop();
        for(R i=h[x];i>1;i=nx[i])
        {
            int y=to[i];
            if(flow[i]&&!d[y])
            {
                q.push(y);
                d[y]=d[x]+1;
                if(y==t)  return 1;
            }
        }
    }
    return 0;
}
inline LL dinic(int x,LL fl)
{
    if(x==t)  return fl;
    LL lft=fl,us;
    int i=now[x];
    for(;i>1&&lft;i=nx[i])
    {
        int y=to[i];
        if(flow[i]&&d[y]==d[x]+1)
        {
            us=dinic(y,min(lft,flow[i]));
            if(!us)  d[y]=0;
            flow[i]-=us;
            flow[i^1]+=us;
            lft-=us;
        }
    }
    now[x]=i;
    return fl-lft;
}
int main()
{
    n=read();m=read();s=read(),t=read();
    while(m--)
    {
        int x=read(),y=read(),z=read();
        add(x,y,z);add(y,x,0);
    }
    LL fl=0;
    while(bfs())
        while(fl=dinic(s,inf))  ans+=fl;
    printf("%lld",ans);
    return 0;
}

附:评测记录

ps:按照题目说法,#10 也不对劲


by 无尽星空 @ 2020-08-10 16:52:36

ppps:

把当前弧改了个位置:48ms

???!!!

只是由

int i=now[x];
    for(;i>1&&lft;i=nx[i])
    {
        int y=to[i];
        if(flow[i]&&d[y]==d[x]+1)
        {
            us=dinic(y,mn(lft,flow[i]));
            if(!us)  d[y]=0;
            flow[i]-=us;
            flow[i^1]+=us;
            lft-=us;
        }
    }
    now[x]=i;

改了now[x]的位置后:

int i=now[x];
    for(;i>1&&lft;i=nx[i])
    {
        now[x]=i;
        int y=to[i];
        if(flow[i]&&d[y]==d[x]+1)
        {
            us=dinic(y,mn(lft,flow[i]));
            if(!us)  d[y]=0;
            flow[i]-=us;
            flow[i^1]+=us;
            lft-=us;
        }
    }

810ms->48ms

问一下各位大佬为什么啊?


by JimmyFlower @ 2020-08-10 16:52:47

当时now放后面就以为没打当前弧(


by Querainy @ 2020-08-10 16:56:51

呃,这么写的话,如果dfs的循环中剩余流量也就是lft=0了,说明当前边很可能没有充满,而此时for循环仍会执行i=nx[i],所以这条边就被跳过了。另一种只写int &i=cut[x]的写法也有类似的问题。

纯属口胡,我是智障


by 无尽星空 @ 2020-08-10 16:58:34

@华山抡剑 您是大佬,我是蒟蒻


by JimmyFlower @ 2020-08-10 16:59:13

@无尽星空 us=dinic(y,mn(lft,flow[i]));这里的递归可能要用到now[x],所以得边赋值边遍历,而不是最后再赋值。我的理解是这样。如果不是求轻喷。


by Querainy @ 2020-08-10 17:17:55

@JimmyFlower 我的意思是,虽然循环终止了,但是在循环终止前又i=nx[i]了一次


by Querainy @ 2020-08-10 17:18:53

@JimmyFlower 递归不可能回到当前点,因为有bfs分层的限制


by JimmyFlower @ 2020-08-10 17:21:03

@华山抡剑 噢我sb了,那没事了


上一页 |