最大流模板——进阶指南整理

喜欢ヅ旅行 2021-12-01 16:48 187阅读 0赞

int d[maxn];
    bool bfs(){
        //在残量网络上构造分层图 
        memset(d,0,sizeof d);
        
        queue<int>q;
        while(q.size())q.pop();
        q.push(s);d[s]=1;
        
        while(q.size()){
            int x=q.front();q.pop();
            for(int i=head[x];i!=-1;i=e[i].nxt){
                int y=e[i].to;
                if(d[y] || e[i].w==0)continue;
                q.push(y);
                d[y]=d[x]+1;
                if(y==t)return 1;
            }
        }
        return 0;
    }
    int dfs(int x,int flow){
        if (x==t)return flow;
        int rest=flow;
        for(int i=head[x];i!=-1 && rest>0;i=e[i].nxt){
            int y=e[i].to;
            if(e[i].w==0 || d[y]!=d[x]+1)continue;
            int k=dfs(y,min(rest,e[i].w));
            if(!k)    d[y]=0;    //y点已经被增广完毕,本次dinic时不会再访问这个点
            e[i].w-=k; e[i^1].w+=k;
            rest-=k;
        }
        return flow-rest;
    } 
    int flow=0,ans=0;
            while(bfs())
                while(flow=dinic(s,inf))
                    ans+=flow;

转载于:https://www.cnblogs.com/zsben991126/p/10994054.html

发表评论取消回复

表情：

评论列表（有 0 条评论，187人围观）

还没有评论，来说两句吧...

相关阅读

相关模板——最小费用最大流

传送门：[QAQQAQ][] 因为要在最大流的情况下，保证最小费用，所以我们在增广时就用SPFA跑一个最短路进行增广，虽然这个路径可能不在最大流中，但残量网络可以保证我们这个

快来打我*/ 2023年06月05日 12:44/ 0 赞/ 48 阅读

相关 C++模板进阶指南：SFINAE

来自于 Substitution failure is not an error 的首字母缩写。Substitution，Failure和Error三个词构成。详细的参考：

本是古典何须时尚/ 2022年12月26日 11:28/ 0 赞/ 96 阅读

相关【C++】模板进阶

模板进阶 1.非类型模板参数 2. 模板的特化 2.1 函数模板特化 2.2 类模板特化 2.2.1 全特化

╰+攻爆jí腚メ/ 2022年10月30日 09:30/ 0 赞/ 117 阅读

相关最大流dinci模板

我们知道，增广路EK算法的时间负责度是O（n\m^2），找最短增广路的时间复杂度是O（m\n^2），所以时间复杂度主要是在找增广路上。这里介绍另一种Dinci算法

矫情吗；*/ 2022年08月10日 14:44/ 0 赞/ 123 阅读

相关 Django模板进阶

本节主要讲 Django模板中的循环，条件判断，常用的标签，过滤器的使用。 1. 列表，字典，类的实例的使用 2. 循环：迭代显示列表，字典等中的内容 3. 条件判断：

ゝ一世哀愁。/ 2022年06月04日 08:41/ 0 赞/ 194 阅读

相关最大流模板(Maximum Flow)

最大流模板(Maximum Flow) 一篇写得通俗易懂介绍最大流的文章:[最大流模板【EdmondsKarp算法，简称EK算法，O(m^2n)】 ][EdmondsKa

秒速五厘米/ 2022年05月23日 05:28/ 0 赞/ 125 阅读

相关 (模板) Dinic 最大流

代码 / DINIC 模板 BEGIN / / 需要的头文件 include <string.h> include <queue> inc

谁借莪１个温暖的怀抱￠/ 2022年04月25日 02:34/ 0 赞/ 122 阅读

相关 Django 模板进阶

本节主要讲 Django模板中的循环，条件判断，常用的标签，过滤器的使用。列表，字典，类的实例的使用循环：迭代显示列表，字典等中的内容条件判断：判断是

谁借莪１个温暖的怀抱￠/ 2022年01月26日 15:53/ 0 赞/ 200 阅读

相关最大流模板——进阶指南整理

int d[maxn]; bool bfs(){ //在残量网络上构造分层图 memset(d,0,sizeof d);

喜欢ヅ旅行/ 2021年12月01日 16:48/ 0 赞/ 188 阅读

相关模板——最小费用最大流

传送门：[QAQQAQ][] 因为要在最大流的情况下，保证最小费用，所以我们在增广时就用SPFA跑一个最短路进行增广，虽然这个路径可能不在最大流中，但残量网络可以保证我们这个

淡淡的烟草味﹌/ 2021年11月01日 13:24/ 0 赞/ 315 阅读