最大网络流dinic

初始化flow（最大流量）为INF（极大值），建边（正向弧和反向弧）
bfs寻找增广路看看有没有路，顺便进行深度标号。如果没有路直接结束输出flow。
如果有，我们按照深度dfs。dfs时注意在给正向弧减权时给反向弧加权。
ans+=flow,重复2到4步骤，直到无路可走。
输出结束~

以上就是网络流全部内容（误

概念什么的就不讲啦~

下面来仔细分析板子代码。

初始化ans=0，构建边
dinic中心：

while(BFS()) ans+=DFS(start,INF);

BFS:

inline bool BFS()

{

    memset(dep,-1,sizeof dep);

        //每次BFS更新深度，-1代表未被更新或者无路径访问

    dep[s]=0;

        //起点的深度为0

    q.push(s);

    while(!q.empty())

    {

        int u=q.front();q.pop();

        for(R int i=head[u];i;i=e[i].nxt)

            if(e[i].dis and dep[e[i].to]==-1)//一定有流并且未被访问

                dep[e[i].to]=dep[u]+1,q.push(e[i].to);

    }

    if(dep[end]==-1)return 0;//如果end的深度为-1，无路径到达，此时最大流

    return 1;

}

ll DFS(int x,ll flow)

{

    if(x==end) return flow;//到终点就返回流

    ll used=0;//优化，记录已用过的流

    for(R int i=head[x];i;i=e[i].nxt)

    {

        int u=e[i].to;

        if(e[i].dis and dep[u]==dep[x]+1)

        {

            long long w=DFS(u,min(e[i].dis,flow-used));//求出最大流

            used+=w;

            e[i].dis-=w;e[i^1].dis+=w;//i^1为相反方向的边，对应加权

            if(used==flow)return flow;

        }

    }

    if(!used)dep[x]=-1;//无流可走，说明此点已经无意义了

    return used;//最大流

}

P3376 【模板】网络最大流

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<queue>

#define R register

#define INF 1<<30

using namespace std;

template <typename T>

inline T read()

{

    T x=0;int w=0;char c=getchar();

    while(!isdigit(c))w|=c=='-',c=getchar();

    while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();

    return w?-x:x;

}

namespace ysr

{

    typedef long long ll;

    const int maxn=100000;

    struct Edge{

        int to,nxt;

        ll dis;

    }e[200000];

    int cur[maxn],head[maxn],ecnt=1;//这里记为-1的原因时便于访问正向弧和反向弧

    int n,m,s,end,dep[maxn];

    inline void addedge(int from,int to,ll dis){

        e[++ecnt].to=to,e[ecnt].nxt=head[from],e[ecnt].dis=dis,head[from]=ecnt;

    }

    inline void add(int from,int to,ll dis){

        addedge(from,to,dis);addedge(to,from,0);

    }

    ll DFS(int x,ll flow)

    {

        if(x==end) return flow;

        ll used=0;

        for(R int i=head[x];i;i=e[i].nxt)

        {

            int u=e[i].to;

            if(e[i].dis and dep[u]==dep[x]+1)

            {

                long long w=DFS(u,min(e[i].dis,flow-used));

                used+=w;

                e[i].dis-=w;e[i^1].dis+=w;

                if(used==flow)return flow;

            }

        }

        if(!used)dep[x]=-1;

        return used;

    }

    queue<int>q;

    inline bool BFS()

    {

        memset(dep,-1,sizeof dep);

        dep[s]=0;

        q.push(s);

        while(!q.empty())

        {

            int u=q.front();q.pop();

            for(R int i=head[u];i;i=e[i].nxt)

                if(e[i].dis and dep[e[i].to]==-1)

                    dep[e[i].to]=dep[u]+1,q.push(e[i].to);

        }

        if(dep[end]==-1)return 0;

        return 1;

    }

    inline void work()

    {

        n=read<int>(),m=read<int>(),s=read<int>(),end=read<int>();

        ll ans=0;

        int a,b;

        ll c;

        for(R int i=0;i<m;i++)a=read<int>(),b=read<int>(),c=read<ll>(),add(a,b,c);

        while(BFS())

            ans+=DFS(s,INF);

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

    }

}

signed main()

{

    ysr::work();

    return 0;

}

大家一定已经发现我定义了一个cur数组不知道但什么的。这其实就是【当前弧优化】的数组，虽然我在上面没有使用。

这也不是什么高深的玩意。我们证明，如果一个点在之前的dfs中已经把一些边考虑过了，由于在当前和以后的流的dfs中这些边都是增广过的，也就是再也没法做出贡献了，那么我们用一个数组cur记录一下考虑到哪里了然后下一侧dfs时接着上次的就行了。

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<queue>

#define R register

#define INF 1<<30

using namespace std;

template <typename T>

inline T read()

{

    T x=0;int w=0;char c=getchar();

    while(!isdigit(c))w|=c=='-',c=getchar();

    while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();

    return w?-x:x;

}

namespace ysr

{

    typedef long long ll;

    const int maxn=100000;

    struct Edge{

        int to,nxt;

        ll dis;

    }e[200000];

    int cur[maxn],head[maxn],ecnt=1;//这里记为-1的原因时便于访问正向弧和反向弧

    int n,m,s,end,dep[maxn];

    inline void addedge(int from,int to,ll dis){

        e[++ecnt].to=to,e[ecnt].nxt=head[from],e[ecnt].dis=dis,head[from]=ecnt;

    }

    inline void add(int from,int to,ll dis){

        addedge(from,to,dis);addedge(to,from,0);

    }

    ll DFS(int x,ll flow)

    {

        if(x==end) return flow;

        ll used=0;

        for(R int i=cur[x];i;i=e[i].nxt)

        {

            cur[x]=i;

            int u=e[i].to;

            if(e[i].dis and dep[u]==dep[x]+1)

            {

                long long w=DFS(u,min(e[i].dis,flow-used));

                used+=w;

                e[i].dis-=w;e[i^1].dis+=w;

                if(used==flow)return flow;

            }

        }

        if(!used)dep[x]=-1;

        return used;

    }

    queue<int>q;

    inline bool BFS()

    {

        for(R int i=0;i<=n;i++)cur[i]=head[i],dep[i]=-1;

        dep[s]=0;

        q.push(s);

        while(!q.empty())

        {

            int u=q.front();q.pop();

            for(R int i=head[u];i;i=e[i].nxt)

                if(e[i].dis and dep[e[i].to]==-1)

                    dep[e[i].to]=dep[u]+1,q.push(e[i].to);

        }

        if(dep[end]==-1)return 0;

        return 1;

    }

    inline void work()

    {

        n=read<int>(),m=read<int>(),s=read<int>(),end=read<int>();

        ll ans=0;

        int a,b;

        ll c;

        for(R int i=0;i<m;i++)a=read<int>(),b=read<int>(),c=read<ll>(),add(a,b,c);

        while(BFS())

            ans+=DFS(s,INF);

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

    }

}

signed main()

{

    ysr::work();

    return 0;

}

还是模板

巴特西

最大网络流dinic

最新文章

热门文章