关于当前弧优化

幻之陨梦 @ 2021-04-03 10:14:01

by 幻之陨梦 @ 2021-04-03 10:14:08

不加当前弧优化代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
    int x=0;int f=1;char c=getchar();
    while(c<'0' || c>'9'){if(c=='-') f=0;c=getchar();}
    while(c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?x:-x;
}
const int N=1e5+10;
int n,m,s,t;
int tot=1,ver[N],edge[N],nxt[N],head[N];
void add(int u,int v,int w)
{
    ver[++tot]=v;
    edge[tot]=w;
    nxt[tot]=head[u];
    head[u]=tot;
}
int d[N];
queue<int>q;
bool bfs()
{
    memset(d,0,sizeof(d));
    while(!q.empty()) q.pop();
    q.push(s);
    d[s]=1;
    while(!q.empty())
    {
        int u=q.front(); q.pop();
        for(int i=head[u];i;i=nxt[i])
        {
            int v=ver[i],w=edge[i];
            if(w && !d[v])
            {
                q.push(v);
                d[v]=d[u]+1;
                if(v==t) return true;
            }
        }
    }
    return false;
}
int dinic(int u,int flow)
{
    if(u==t) return flow;
    int rest=flow,k;
    for(int i=head[u];i && rest;i=nxt[i])
    {
        int v=ver[i],w=edge[i];
        if(w && d[v]==d[u]+1)
        {
            k=dinic(v,min(rest,w));
            if(!k) d[v]=0;
            edge[i]-=k;
            edge[i^1]+=k;
            rest-=k;
        }
    }
    return flow-rest;
}
int flow,ans;
signed main()
{
    n=read(),m=read(),s=read(),t=read();
    for(int i=1;i<=m;i++)
    {
        int u=read(),v=read(),w=read();
        add(u,v,w);
        add(v,u,0);
    }
    while(bfs())
        while((flow=dinic(s,INT_MAX))) ans+=flow;
    printf("%lld",ans);
    return 0;
}

加了当前弧优化代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
    int x=0;int f=1;char c=getchar();
    while(c<'0' || c>'9'){if(c=='-') f=0;c=getchar();}
    while(c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?x:-x;
}
const int N=1e4+5;
int n,m,s,t;
int tot=1,ver[N],edge[N],nxt[N],head[205],cur[205];
void add(int u,int v,int w)
{
    ver[++tot]=v;
    edge[tot]=w;
    nxt[tot]=head[u];
    head[u]=tot;
}
int d[N];
queue<int>q;
bool bfs()
{
    memcpy(cur,head,sizeof(head));
    memset(d,0,sizeof(d));
    while(!q.empty()) q.pop();
    q.push(s);
    d[s]=1;
    while(!q.empty())
    {
        int u=q.front(); q.pop();
        for(int i=head[u];i;i=nxt[i])
        {
            int v=ver[i],w=edge[i];
            if(w && !d[v])
            {
                q.push(v);
                d[v]=d[u]+1;
                if(v==t) return true;
            }
        }
    }
    return false;
}
int dinic(int u,int flow)
{
    if(u==t) return flow;
    int rest=flow,k;
    for(int &i=cur[u];i && rest;i=nxt[i])
    {
        int v=ver[i],w=edge[i];
        if(w && d[v]==d[u]+1)
        {
            k=dinic(v,min(rest,w));
            if(!k) d[v]=0;
            edge[i]-=k;
            edge[i^1]+=k;
            rest-=k;
        }
    }
    return flow-rest;
}
int flow,ans;
signed main()
{
    n=read(),m=read(),s=read(),t=read();
    for(int i=1;i<=m;i++)
    {
        int u=read(),v=read(),w=read();
        add(u,v,w);
        add(v,u,0);
    }
    while(bfs())
        while((flow=dinic(s,INT_MAX))) ans+=flow;
    printf("%lld",ans);
    return 0;
}

by expect @ 2021-04-03 10:17:43

你每bfs一遍要还原cur啊，这咋过的

by expect @ 2021-04-03 10:17:59

@幻之陨梦

by 幻之陨梦 @ 2021-04-03 10:31:38

@expect 我在bfs里面加了啊，跟OI-wiki学的

by Coros_Trusds @ 2021-04-03 10:32:12

//2021/4/1

//2021/4/2

//2021/4/3

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <queue>

using namespace std;

const int INF=0x7fffffff;

const int MA=100005;

const int ma=20005;

struct Node
{
    int v;

    int val;

    int nxt;
};

Node node[MA];

int head[ma],cur[ma],dep[ma];

bool inque[ma];

int top=1;

int n,m,s,t;

inline void add(int u,int v,int w)
{
    top++;

    node[top].v=v;

    node[top].val=w;

    node[top].nxt=head[u];

    head[u]=top;
}

inline bool bfs()
{
    queue<int>q;

    memset(inque,false,sizeof(inque));

    memset(dep,0x3f,sizeof(dep));

    q.push(s);

    inque[s]=true;

    dep[s]=0;

    while(!q.empty())
    {
        int u=q.front();

        q.pop();

        for(register int i=head[u];i;i=node[i].nxt)
        {
            int d=node[i].v;

            if(inque[d]==false && node[i].val>0)
            {
                inque[d]=true;

                q.push(d);

                dep[d]=dep[u]+1;
            }
        }
    } 

    return dep[t]!=0x3f3f3f3f;
}

inline int dfs(int u,int flow)
{
    int rlow=0;

    if(u==t)
    {
        return flow;
    }

    for(register int &i=cur[u];i;i=node[i].nxt)
    {
        int d=node[i].v;

        if(dep[d]==dep[u]+1 && node[i].val>0)
        {
            if(rlow=dfs(d,min(node[i].val,flow)))
            {
                node[i].val-=rlow;

                node[i^1].val+=rlow;

                return rlow;
            }
        } 
    }

    return 0;
}

long long maxflow;

inline long long Dinic()
{
    long long lowflow;

    while(bfs())
    {
        for(register int i=0;i<=ma;i++)
        {
            cur[i]=head[i];
        }

        while(lowflow=dfs(s,INF))
        {
            maxflow+=lowflow;
        }
    }

    return maxflow;
}

int main()
{
    scanf("%d%d%d%d",&n,&m,&s,&t);

    for(register int i=1;i<=m;i++)
    {
        int u,v,w;

        scanf("%d%d%d",&u,&v,&w);

        add(u,v,w);

        add(v,u,0);
    }

    printf("%lld\n",Dinic());

    return 0;
}

by metaphysis @ 2021-04-03 12:18:57

@幻之陨梦

一方面是测试数据的原因，边的规模较小，当前弧优化体现不出优势，另外一个和您的实现也有一定关系。

by 幻之陨梦 @ 2021-04-03 13:02:10

@metaphysis 请问怎么实现才能更快啊/kk

by metaphysis @ 2021-04-03 15:50:32

@幻之陨梦

回复。

by 幻之陨梦 @ 2021-04-03 20:50:38

@metaphysis Thanks♪(･ω･)ﾉ