首页 > 其他 > 详细

【MOBAN】网络流之最大流dinic的模板luoguP2740草地排水

时间:2021-09-24 19:28:46      阅读:20      评论:0      收藏:0      [点我收藏+]

感觉网络流已经废了。。勉强背背dinic板子


关于dinic的想法其实来自于一个简易的最大流,每次找到一条增广路然后dfs跑一次,即一次bfs一次dfs一条路。

可是我们bfs跑出的分层图很可能会跑出多条增广路,于是我们dfs的时候将所有可能的增广路跑完。

关于当前弧优化,即我们每次边在跑dfs的时候如果已经将一条路榨干,那么在该分层图跑下一次dfs的时候就可以跳过这条路。具体做法我们建完分层图用cur[]复制原本的head[]数组,然后在cur上跑,cur榨干一条路即更改值到下一条路,于是就不会再重复浏览该路。

还有一个小优化不知道有没有用,就是发现一个点一滴水都不能增广则直接将该点从分层图中去除。

点击查看代码
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

using namespace std;
const int maxn = 1e4+5;

int N,M;
int en[maxn],nt[maxn],la[maxn],cla[maxn],owo=1,len[maxn];
void adg(int x,int y,int z) {
    en[++owo] = y; nt[owo]=cla[x]; cla[x]=owo; len[owo]=z;
    en[++owo] = x; nt[owo]=cla[y]; cla[y]=owo; len[owo]=0;
}
int qe[maxn],qf,qm,dis[maxn];
bool bfs() {
    qf = qm = 1; qe[1] = 1; dis[1] = 0;
    for(int i=2;i<=M;i++) dis[i] = -1;
    while(qf<=qm) {
        int x = qe[qf++];
        for(int it=cla[x];it;it=nt[it]) {
            int y = en[it];
            if(dis[y]==-1&&len[it]>0) {
                dis[y] = dis[x] + 1;
                qe[++qm] = y;
            }
        }
    }
    return dis[M]!=-1;
}
int dfs(int x,int flow) {
    if(x==M) return flow;
    int re = 0;
    for(int &it=la[x];it;it=nt[it]) {
        int y = en[it];
        if(dis[y]==dis[x]+1&&len[it]>0) {
            int ff = dfs(y,min(len[it],flow));
            flow -= ff; re += ff;
            len[it] -= ff; len[it^1] += ff;
            if(!flow) break;
        }
    }
    if(!re) dis[x] = -1;
    return re; 
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++) {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        adg(x,y,z);
    }
    int ans = 0;
    //dinic
    while(bfs()) {
        for(int i=1;i<=M;i++) la[i] = cla[i];
        ans += dfs(1,0x3f3f3f3f);
    }
    printf("%d",ans);
    return 0;
}

【MOBAN】网络流之最大流dinic的模板luoguP2740草地排水

原文:https://www.cnblogs.com/newuser233/p/15306693.html

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!