10

【网络流相关】最大流的Dinic算法实现

 4 years ago
source link: http://www.cnblogs.com/notscience/p/12007035.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

Luogu P3376

\(EK\) 算法求最大流时每一次只求一条增广路,时间复杂度会比较高。尽管实际应用中表现比较优秀,但是有一些题目还是无法通过。

那么我们就会使用 \(Dinic\) 算法实现多路增广。

算法的基本流程如下:

  1. \(BFS\) 对图进行分层,求出终点所在的层数
  2. \(DFS\) 对每一条增广路的信息进行更新

仅仅这样看,虽然一次 \(BFS\) 能找到多条最短增广路,但是信息的更新仍然是逐条增广路进行更新,效率上并没有太大变化。

所以我们需要下面的两个优化:

  • 记录起点到节点 \(P\) 的流 \(flow\) 和节点 \(P\) 到终点的流 \(used\) 。若 \(flow=used\) ,则不必再进行之后的 \(DFS\) 了,可以直接回溯。
  • 使用一个 \(cur\) 数组复制链式前向星的 \(head\) 数组,在 \(DFS\) 时, \(cur\) 数组记录当前处理的边的编号。下次 \(DFS\) 到这个节点时,可以直接从 \(cur\) 数组记录的那条边开始。

第二个优化我们称之为 当前弧优化

原理:每一条已经处理完毕的边,必然不能再容纳下更多的流了。

\(Dinic\) 的时间复杂度是 \(O(n^2m)\) 。对于二分图匹配问题, \(Dinic\) 的时间复杂度是 \(O(m\sqrt n)\)

结合代码进行理解

#include<cstdio>
#include<queue>
using namespace std;
int n,m,num,cnt,u,v,head[20005],cur[20005],dis[20005],ans;
bool vis[20005];
struct data
{
    int to,next,val;
}e[5000005];
void add(int u,int v,int val)
{
    e[++cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
    e[cnt].val=val;
}
bool bfs(int s,int t)
{
    queue<int> que;
    que.push(s);
    for (int i=1;i<=n;i++) dis[i]=0,vis[i]=false,cur[i]=head[i];
    vis[s]=true;
    dis[s]=1;
    while (!que.empty())
    {
        int now=que.front();
        que.pop();
        for (int i=head[now];i;i=e[i].next)
        {
            v=e[i].to;
            if (!vis[v]&&e[i].val>0)
            {
                dis[v]=dis[now]+1;
                vis[v]=true;
                if (v==t) return true;
                que.push(v);
            }
        }
    }
    return false;
}
int dfs(int now,int t,int flow)
{
    if (!flow||now==t) return flow;
    int used=0;
    for (int i=cur[now];i;i=e[i].next)
    {
        cur[now]=i;//当前弧优化
        v=e[i].to;
        if (dis[now]+1!=dis[v]) continue;
        int tmp=dfs(v,t,min(flow-used,e[i].val));
        if (tmp)
        {
            e[i].val-=tmp;
            e[i^1].val+=tmp;
            used+=tmp;
            if (flow-used==0) return flow;
        }
    }
    return used;
}
void Dinic(int s,int t)
{
    while (bfs(s,t)) ans+=dfs(s,t,0x7fffffff);
}
int main()
{
    int s,t,w;
    scanf("%d%d%d%d",&n,&m,&s,&t);
    cnt=1;
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        add(v,u,0);
    }
    Dinic(s,t);
    printf("%d",ans);
    return 0;
}

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK