Dinic当前弧优化模板及教程

在阅读本文前，建议先自学最大流的Ek算法。

引入

Ek的核心是执行bfs，一旦找到增广路就停下来进行增广。换言之，执行一遍BFS执行一遍DFS，这使得效率大大降低。于是我们可以考虑优化。

核心思路

在一次BFS中，找到的增广路可能不止一条，这时我们可以本着“尽量少进行BFS”的想法，在一次bfs后把所有能增广的路径全部增广。
具体怎么做呢？
仍然是：
while（bfs（源点，汇点）） dfs（）；

每次bfs标记出每个点的“深度”，也就是距离源点的长度。我们将得到的新图称作分层图。接下来我们在分层图上进行增广，把能增广的路径全部增广。
其它部分和Ek大体相同。

关于当前弧优化

其实是一个很强的优化

每次增广一条路后可以看做“榨干”了这条路，既然榨干了就没有再增广的可能了。但如果每次都扫描这些“枯萎的”边是很浪费时间的。那我们就记录一下“榨取”到那条边了，然后下一次直接从这条边开始增广，就可以节省大量的时间。这就是当前弧优化

具体怎么实现呢，先把链式前向星的head数组复制一份，存进cur数组，然后在cur数组中每次记录“榨取”到哪条边了。

Code

//by floatiy

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<queue>

using namespace std;

const int MAXN =  + ;

const int MAXM =  + ;

const int INF = 1e9;

int n,m;

int s,t;//源点 汇点

int maxflow;//答案

struct Edge {

    int next;

    int to,flow;

} l[MAXM << ];

int head[MAXN],cnt = ;

int deep[MAXN],cur[MAXN];//deep记录bfs分层图每个点到源点的距离

queue <int> q;

inline void add(int x,int y,int z) {

    cnt++;

    l[cnt].next = head[x];

    l[cnt].to = y;

    l[cnt].flow = z;

    head[x] = cnt;

    return;

}

int min(int x,int y) {

    return x < y ? x : y;

}

int dfs(int now,int t,int lim) {//分别是当前点，汇点，当前边上最小的流量

    if(!lim || now == t) return lim;//终止条件

//  cout<<"DEBUG: DFS HAS BEEN RUN!"<<endl;

    int flow = ;

    int f;

    for(int i = cur[now]; i; i = l[i].next) {//注意！当前弧优化

        cur[now] = i;//记录一下榨取到哪里了

        if(deep[l[i].to] == deep[now] +  //谁叫你是分层图

            && (f = dfs(l[i].to,t,min(lim,l[i].flow)))) {//如果还能找到增广路

        flow += f;

            lim -= f;

            l[i].flow -= f;

            l[i ^ ].flow += f;//记得处理反向边

            if(!lim) break;//没有残量就意味着不存在增广路

        }

    }

    return flow;

}

bool bfs(int s,int t) {

    for(int i = ; i <= n; i++) {

        cur[i] = head[i];//拷贝一份head，毕竟我们还要用head

        deep[i] = 0x7f7f7f7f;

    }

    while(!q.empty()) q.pop();//清空队列 其实没有必要了

    deep[s] = ;

    q.push(s);

    while(!q.empty()) {

        int tmp = q.front();

        q.pop();

        for(int i = head[tmp]; i; i = l[i].next) {

            if(deep[l[i].to] > INF && l[i].flow) {//有流量就增广

            //deep我赋的初值是0x7f7f7f7f 大于 INF = 1e9）

                deep[l[i].to] = deep[tmp] + ;

                q.push(l[i].to);

            }

        }

    }

    if(deep[t] < INF) return true;

    else return false;

}

void dinic(int s,int t) {

    while(bfs(s,t)) {

        maxflow += dfs(s,t,INF);

//      cout<<"DEBUG: BFS HAS BEEN RUN!"<<endl;

    }

}

int main() {

    cin>>n>>m;//点数边数

    cin>>s>>t;

    int x,y,z;

    for(int i = ; i <= m; i++) {

        scanf("%d%d%d",&x,&y,&z);

        add(x,y,z);

        add(y,x,);

    }

//  cout<<"DEBUG: ADD FININSHED!"<<endl;

    dinic(s,t);

    printf("%d",maxflow);

    return ;

}

巴特西

Dinic当前弧优化模板及教程

引入

核心思路

关于当前弧优化

Code

最新文章

热门文章

巴特西

Dinic当前弧优化 模板及教程

引入

核心思路

关于当前弧优化

Code

最新文章

热门文章

Dinic当前弧优化模板及教程