首页 > 编程语言 >网络流最大流Dinic算法

网络流最大流Dinic算法

时间:2023-12-08 21:14:06浏览次数:39  
标签:mf cur 容量 int LL 上限 网络 算法 Dinic

感谢董晓老师:博客b站

/*  
    Dinic算法的思路是,用bfs进行分层,限制后面dfs每次的搜索深度,
    并且,在dfs的过程中,直接把当前这个路走到u的容量限制分给u的各个出边
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 10020, M = 200020;
typedef long long LL;
struct Edge
{
    LL v, c, ne;
} e[M];

int n, m, S, T;

int h[N], idx = 1; // 由于有反向边,所以边要两两配对,这里放弃01这一对,从2,3开始配对

int d[N];   // d数组存储的是每个点在这一轮的层次
int cur[N]; // cur[u]用于存储上次沿着某个路走到u这个点的容量是分配到那个出边被耗完的

void add(int a, int b, int c)
{
    e[++idx] = {b, c, h[a]};
    h[a] = idx;
}
bool bfs()
{
    memset(d, 0, sizeof d); // 每次bfs要重新分层,所以每次一开始要做的是层次初始化为0,同时也可以用d数组判定是否遍历过
    //! 这里因为写成sizeof 0错了
    queue<int> q;

    q.push(S);
    d[S] = 1; // 层次从1开始

    while (q.size())
    {
        auto u = q.front();
        q.pop();

        for (int i = h[u]; i; i = e[i].ne)
        {
            auto v = e[i].v;

            if (d[v] == 0 && e[i].c) // 如果这一次bfs还没有遍历到v,并且uv这条路剩余容量上限不为0
            {
                d[v] = d[u] + 1;
                q.push(v);
                if (v == T)
                    return true; // 只要找到了T就行,找到了T说明T是最深的一层,那么就是说,其他的点都找过了,因此可以直接退出来
            }
        }
    }
    return false;
}

LL dfs(int u, LL mf) // 深搜,不断把当前这条都到u的路的容量上限mf分配给u的各个出边
// 并且返回一共分了多少出去
{
    if (u == T)
    {
        return mf; // 如果这个点是汇点,那么就不用往后分了,或者说可以认为是T后面可以分无限多,所以分出去的就是mf
    }

    LL sum = 0; // 用于记录分了多少出去

    for (int i = cur[u]; i; i = e[i].ne) // cur[u]一开始存储的是h[u]也就是u的第一个出边的编号,这里cur用于存储上一次dfs到u是在到个边把容量量上限耗完的,之所以前面的边不用管,是因为一定把那些边都填到上限了才会到这个边
    {
        cur[u] = i; //! 更新当前弧,这也叫当前弧优化

        auto v = e[i].v;
        if (d[v] == d[u] + 1 && e[i].c)     // 为了限制深搜的深度,要根据bfs分的层来遍历,并且要求这个边剩余的容量上限不为0
        {                                   //! 这里曾经因为等于写成赋值错了
            LL f = dfs(v, min(mf, e[i].c)); // 走到v的容量上限是之前走到u的容量上限mf和(u,v)这条边的上限取min,这里是要递归的去求让v把能留到t的容量上限尽可能多的分出去
            e[i].c -= f;                    // (u,v)这条边的容量会减去从v分走的流量
            e[i ^ 1].c += f;                // 反向边
            sum += f;                       // 从u出去的总流量要加上从v出去的总流量
            mf -= f;                        // 走到u的容量上限被v拿去消耗了
            if (mf == 0)
                break; // 如果mf已经被消耗完了,说明这次走到u的容量限制已经没有了,直接退出循环,不用再找u的其他子节点了
            //! 余量优化
        }
    }
    if (sum == 0)
    {
        d[u] = 0; // 如果sum=0,说明从u这个点已经无法把流量分出去了,所以u这个点的层次设为0,以后不用再遍历u了
    }             //! 残枝优化

    return sum; // 返回当前这个点可以分出去多少流量
}

LL dinic()
{
    LL flow = 0;

    while (bfs()) // bfs用于给点分层,返回是否能遍历到T,如果不能就说明图已经没有可以走得增广路了,找不到可行流了
    {
        memcpy(cur, h, sizeof h); // 将cur初始为每个点的第一个出边
        flow += dfs(S, 1e9);      // 一开始从S开始,容量上限设为无穷大
    }
    return flow;
}

int main()
{
    cin >> n >> m >> S >> T;
    int a, b, c;
    while (m--)
    {

        cin >> a >> b >> c;

        add(a, b, c);
        add(b, a, 0); // 返现边容量上限初始为0
    }

    cout << dinic() << endl;

    return 0;
}

标签:mf,cur,容量,int,LL,上限,网络,算法,Dinic
From: https://www.cnblogs.com/z4t15/p/17889027.html

相关文章

  • 2023-2024-1 20232311 《网络空间安全导论》 第五章学习
    教材学习内容总结思维导图教材学习中的问题和解决过程问题1:除计算机技术外,还有哪些领域需要协同工作来更好地保证信息内容的安全问题1解决方案(询问ChatGPT)问题2:如何基于网络交互重构机制实现需要身份认证的动态网页发布信息获取问题2解决方案(询问ChatGPT)基于AI的学习......
  • 深入研究与优化目标检测算法,以提高其性能与适用性的探索性研究
    基于深度学习的目标检测算法分为2类:TwoStage和OneStage。TwoStage:先预设一个区域,改区域称为regionproposal,即一个可能包含待检测物体的预选框(简称RP),再通过卷积神经网络进行样本分类计算。流程是:特征提取->生成RP->分类/回归定位。常见的TwoStage算法有:R-CNN、SPP-Net、Fa......
  • 图注意力网络
    ICLR2018Abstract​ 我们提出了图注意网络(GATs),这是一种新型的神经网络架构,在图结构的数据上进行操作,利用掩蔽的自注意层来解决先前基于图卷积或其近似的方法的缺点。通过堆叠层,其中的节点能够关注其邻域的特征,我们能够(隐含地)为邻域的不同节点指定不同的权重,而不需要任何昂贵的......
  • 杂算法
    updateon2023.11.17NOIP前来复习板子,发现KMP整理的不是很到位,所以更新详细一些。模板题抽象的blog浅显易懂的讲解视频:(dalao讲得太好了\(%%%\))备用网址\(kmp\)(字符串匹配)的概念:主串:被匹配的字符串模式串:匹配的串最长前后缀:一个字符串某个前缀后后缀相同,而且长度尽可......
  • 数据结构与算法----------3
    队列队列也是一种受限制的线性表,只能在一端进行插入,在另一端进行删除。当然也有一种特殊的队列,名叫双端队列,也就是一段既可以插入也可以删除,在另一端也可以插入和删除。这就是双端队列。队列的顺序实现(非环形数组)代码实现//队列的顺序实现(非环形数组)#define_CRT_SECUR......
  • 二分——acwing算法基础课笔记
    个人笔记,欢迎补充、指正。此次完全以个人理解来写。整数二分 整数二分有两种,分别是找左边界和找右边界。 寻找符合要求的左边界:绿色点intbsearch_1(intl,intr){while(l<r){intmid=l+r>>1;//对应下界,最左if(check(mid))r=......
  • 数据结构与算法---------2
    栈栈是一个具有一定操作约束的线性表,只能在一端(栈顶,top)做插入和删除。栈的顺序实现//栈的顺序实现#define_CRT_SECURE_NO_WARNINGS#include<stdio.h>#include<stdlib.h>#include<string.h>#include<math.h>#include<time.h>#include<stdbool.h>#defineuun......
  • “古剑山”第一届全国大学生网络攻防大赛-Crypto WP
    CryptobabyRSA题目信息p=10557060480607393156040418736281630895040877491596075167695884580033587151860045514604024031420460694464109891485815938658886878598710052458169904360535195234858613255345870229839390747695594699084944203444188274827818114850332930966......
  • 矿山自救器检测的AI算法工作原理是什么?在智慧矿山应用广吗?
    智慧矿山作为当今矿业领域的热门话题,其应用已经逐渐成为行业发展的必然趋势。在智慧矿山中,矿山自救器检测的AI算法是一个重要的组成部分,通过这一技术,可以大大提高矿工的安全水平和生产效率。那么,矿山自救器检测的AI算法工作原理是什么?在智慧矿山应用广泛吗?接下来,我们将从技术原理和......
  • 【EMNLP 2023】基于知识迁移的跨语言机器阅读理解算法
    近日,阿里云人工智能平台PAI与华南理工大学朱金辉教授团队、达摩院自然语言处理团队合作在自然语言处理顶级会议EMNLP2023上发表基于机器翻译增加的跨语言机器阅读理解算法X-STA。通过利用一个注意力机制的教师来将源语言的答案转移到目标语言的答案输出空间,从而进行深度级别的辅助......