当前位置：首页 > news >正文

图论---最大流（Dinic）

news 来源：原创 2025/6/14 12:04:18

最大流一定是阻塞流，阻塞流不一定是最大流。

阻塞流---从起点到终点的管道已经阻塞了。

时间复杂度：
- 一般情况：O(n2m)O(n2m)（但实际运行效率较高，尤其在稀疏图上）。
- 使用当前弧优化后，效率接近 O(nmlog⁡C)O(nmlogC)（CC 是最大容量）。

代码优化建议

改用链式前向星（如边数 m > 1e5 时更高效）。
预分配 vector 空间（如 v[a].reserve(10) 减少动态扩容开销）。
改用 int 代替 unsigned long long（除非题目明确要求大容量）。

省赛/ICPC：此代码足够应对大多数网络流题目（点数 n ≤ 500，边数 m ≤ 1e4）。
更高阶优化：如需处理更大数据（如 n ≤ 1e5），需改用 ISAP 或 HLPP 算法。

步骤：1、BFS分层

2、DFS增广

#include<bits/stdc++.h>
using namespace std;#define int unsigned long long  // 使用 unsigned long long 防止溢出
const int MN = 500;            // 最大点数
const int INF = 0x3f3f3f3f;    // 无穷大
int n, m, s, t;               // 点数、边数、源点、汇点
int cur[MN], dep[MN];         // cur: 当前弧优化数组；dep: 层次深度
struct Node { int v, k, id; }; // 边的结构体：v=目标点，k=剩余容量，id=反向边索引
vector<Node> v[MN];           // 邻接表存图bool bfs() {queue<int> q;memset(dep, -1, sizeof(dep));  // 初始化 dep 为 -1dep[s] = 0;                    // 源点深度为 0q.push(s);while (!q.empty()) {int x = q.front();q.pop();for (int i = 0; i < v[x].size(); i++) {int y = v[x][i].v;int k = v[x][i].k;if (dep[y] == -1 && k > 0) {  // 未访问过且剩余容量 > 0dep[y] = dep[x] + 1;       // 更新深度q.push(y);}}}memset(cur, 0, sizeof(cur));  // 重置当前弧优化return dep[t] != -1;           // 返回是否能到达汇点
}int dfs(int x, int ans) {if (x == t) return ans;  // 到达汇点，返回当前流量for (int i = cur[x]; i < v[x].size(); i++) {int y = v[x][i].v;int k = v[x][i].k;int id = v[x][i].id;cur[x] = i;  // 当前弧优化，避免重复访问if (dep[y] == dep[x] + 1 && k > 0) {  // 必须在下一层且剩余容量 > 0int tmp = dfs(y, min(k, ans));     // 递归找增广路径if (tmp > 0) {                    // 找到可行流v[x][i].k -= tmp;              // 更新正向边容量v[y][id].k += tmp;             // 更新反向边容量return tmp;} else {dep[y] = -1;  // 剪枝：该点无法到达汇点，标记为无效}}}return 0;  // 无增广路径
}int dinic() {int ans = 0, tmp;while (bfs()) {         // 只要还能分层（存在增广路径）while (tmp = dfs(s, INF)) {  // 多路增广ans += tmp;     // 累加流量}}return ans;
}void add(int a, int b, int k) {int sza = v[a].size(), szb = v[b].size();v[a].push_back({b, k, szb});   // 正向边v[b].push_back({a, 0, sza});    // 反向边（初始容量为 0）
}signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> n >> m >> s >> t;for (int i = 1; i <= m; i++) {int a, b, k;cin >> a >> b >> k;add(a, b, k);  // 建图}cout << dinic();  // 计算最大流return 0;
}

图论---最大流（Dinic）

最大流一定是阻塞流，阻塞流不一定是最大流。阻塞流---从起点到终点的管道已经阻塞了。时间复杂度： 一般情况：O(n2m)O(n2m)（但实际运行效率较高，尤其在稀疏图上）。使用当前弧优化后，效率接近…...

编程日记 2025/5/28 11:56:47

FastAPI系列06：FastAPI响应（Response）

FastAPI响应（Response） 1、Response入门2、Response基本操作设置响应体（返回数据）设置状态码设置响应头设置 Cookies 3、响应模型 response_model4、响应类型 response_classResponse派生类自定义response_class 在“FastAPI系列0…...

编程日记 2025/5/26 20:29:36

双目RealSense系统配置rs_camera.launch----实现D435i自制rosbag数据集到离线场景的slam建图

引言 Intel RealSense系列相机因其出色的深度感知能力和灵活的配置选项，在机器视觉与应用中得到广泛应用。大家在后期的slam学习中，无论是对算法本身的性能要求还是实验的泛化性都有一定的要求，那么公开的数据集如kitti、tum、Eourc不能满足…...

编程日记 2025/5/19 19:40:00

【MCP-2】MCP是什么，利用智普大模型在MaxKB中调用自己开发的MCP服务

在上一篇【MCP-1】MCP是什么，从DEMO入手文章中我们介绍了MCP是什么、他能干啥，以及简单的Demo示例等，这篇文章我们使用MaxKB这个工具，利用智普大模型，看看MCP到底怎么用。创建SSE协议的MCP服务在上篇文章中的Demo是…...

编程日记 2025/5/28 15:04:48

Allegro23.1新功能之如何单独关闭铜皮显示效果操作指导

Allegro23.1新功能之如何单独关闭铜皮显示效果操作指导 Allegro升级到了23.1的时候，支持单独关闭铜皮显示，如下图如何仅关闭shape的显示，单独显示线，具体操作如下点击setup...

编程日记 2025/6/1 18:21:48

《从分遗产说起：JS 原型与继承详解》

“天天开心就好” 先来讲讲概念： 原型（Prototype） 什么是原型？ 原型是 JavaScript 中实现对象间共享属性和方法的机制。每个 JavaScript 对象（除了 null）都有一个内部链接指向另一个对象，这…...

编程日记 2025/5/22 7:11:30

【Part 2安卓原生360°VR播放器开发实战】第二节｜基于等距圆柱投影方式实现全景视频渲染

《VR 360全景视频开发》专栏将带你深入探索从全景视频制作到Unity眼镜端应用开发的全流程技术。专栏内容涵盖安卓原生VR播放器开发、Unity VR视频渲染与手势交互、360全景视频制作与优化，以及高分辨率视频性能优化等实战技巧。 📝 希望通过这个专栏&am…...

编程日记 2025/5/29 18:14:00

RecyclerView的使用依赖 implementation("androidx.recyclerview:recyclerview:1.4.0")activity_recyclerview.xml <androidx.recyclerview.widget.RecyclerViewandroid:id"id/rv"android:layout_width"match_parent"android:layout_height…...

编程日记 2025/5/27 8:26:14

跨域问题（Cross-Origin Problem）

跨域问题（Cross-Origin Problem）是浏览器出于安全考虑，对不同源（协议、域名、端口）之间的资源访问进行限制而引发的限制。以下是详细解释： 1. 核心定义跨域：当一个网页（源A&#x…...

编程日记 2025/5/18 11:21:13

阿里云直接对系统云盘扩容

阿里云直接对系统云盘扩容登录阿里云控制台，进入ECS实例管理页面，检查目标磁盘的容量是否已更新为扩容后的数值。通过SSH远程连接服务器，使用命令 lsblk 或 fdisk -l 查看当前磁盘分区和容量，确认扩容后的物理磁盘已被系统识别。…...

编程日记 2025/5/26 7:28:48

Java大厂面试突击：从Spring Boot自动配置到Kafka分区策略实战解析

第一轮核心知识面试官：请解释Spring Boot中自动配置的工作原理并演示如何自定义一个ConfigurationProperties组件？ xbhog：自动配置通过EnableAutoConfiguration注解触发，结合当前环境判断（如是否检测到MyBatis依赖&…...

编程日记 2025/5/29 17:52:48

【python】lambda用法（结合例子理解）

目录 lambda 是什么？为什么叫 lambda？语法举例 1. 最简单的 lambda：单个数字处理 2. 用 lambda 排序一组字符串（按照长度排序） 3. 在列表里找出绝对值最小的数字 4. 给 map() 用 lambda 5. 组合使用：筛选出偶数 lambda 和 def 的对比 lambda 适合用在什么地…...

编程日记 2025/5/29 9:55:42

前端Ui设计工具

PS 稿、蓝湖、Sketch 和 Figma 前端 UI 设计工具的对比分析 PS 稿（Adobe Photoshop） 提供精准设计细节：PS 稿能让前端更精准地理解页面布局、元素尺寸、颜色等，通过精确测量和查看信息面板，把握设计元素的空间关系、…...

编程日记 2025/5/27 7:12:42

深入探索Python Pandas：解锁数据分析的无限可能

放在前头深入探索Python Pandas：解锁数据分析的无限可能深入探索Python Pandas：解锁数据分析的无限可能在当今数据驱动的时代，高效且准确地处理和分析数据成为了各个领域的关键需求。而Python作为一门强大且灵活的编程语言，…...

编程日记 2025/5/29 21:20:11

django admin 设置字段不可编辑

在Django中，如果你想让管理员在后台管理界面中无法编辑某个字段，你可以通过在模型的Meta类中设置editable属性为False，或者在admin.py文件中使用readonly_fields属性来实现。方法1：在模型中使用Meta类设置你可以在模型的Meta类…...

编程日记 2025/6/4 11:50:25

AI在医疗领域的10大应用：从疾病预测到手术机器人

AI在医疗领域的10大应用：从疾病预测到手术机器人系统化学习人工智能网站（收藏）：https://www.captainbed.cn/flu 文章目录 AI在医疗领域的10大应用：从疾病预测到手术机器人摘要引言1. 医学影像诊断：从静态…...

编程日记 2025/6/1 11:44:56

深入理解 Java 单例模式：从基础到最佳实践

单例（Singleton）模式是 Java 中最基本、最常用的设计模式之一。它确保一个类在任何情况下都只有一个实例，并提供一个全局访问点来获取这个唯一的实例。一、为什么需要单例模式？（使用场景） 单例模式主要适…...

编程日记 2025/5/29 21:18:29

Rust：安全与性能兼得的现代系统编程语言

一、起源与设计理念 Rust 是由 Mozilla 研究院 Graydon Hoare 于 2006 年发起设计的系统级编程语言，其诞生源于传统系统语言（如 C/C）在内存安全与并发编程方面的缺陷。经过近十年的迭代，Rust 1.0 稳定版于 2015 年正式发布&#…...

编程日记 2025/5/30 21:57:53

AI赋能智慧医疗新范式：小天互连即时通讯打造高效、安全的医疗通讯平台

在医疗行业，高效的信息协作与严格的数据安全不仅直接关系患者诊疗效率，更是医院现代化管理的核心命题。小天互连即时通讯系统通过将智能化功能与医疗场景深度结合，打造出全链路数字化协作平台，有效破解了传统沟通模式的效率瓶颈&a…...

编程日记 2025/5/20 14:19:29

图像生成新势力：GPT-Image-1 与 GPT-4o 在智创聚合 API 的较量

在人工智能领域，图像生成技术正迅速发展，OpenAI 推出的 GPT-Image-1 和 GPT-4o 在图像生成方面展现出了强大的能力。智创聚合 API 平台已支持这两个模型，并且其图片生成 / 编辑工作台支持图片的循环编辑等功能，为用户提供了更便捷…...

编程日记 2025/5/26 14:48:37

如何避免爬虫因Cookie过期导致登录失效

1. Cookie的作用及其过期机制 1.1 什么是Cookie？ Cookie是服务器发送到用户浏览器并保存在本地的一小段数据，用于维持用户会话状态。爬虫在模拟登录后，通常需要携带Cookie访问后续页面。 1.2 Cookie为什么会过期？ 会话Cookie&…...

编程日记 2025/5/27 17:07:30

集成方案 | Docusign + 甄零科技，赋能企业海外业务高效增长！

本文将详细介绍 Docusign 与甄零科技的集成步骤及其效果，并通过实际应用场景来展示 Docusign 的强大集成能力，以证明 Docusign 集成功能的高效性和实用性。甄零科技是一家专注于数字化合同管理系统的 SaaS 解决方案提供商，致力于为企业打造“…...

编程日记 2025/5/31 15:16:38

【Arxiv 2025】Single Image Iterative Subject-driven Generation and Editing

文章目录文章标题作者及研究团队介绍01 在论文所属的研究领域，有哪些待解决的问题或者现有的研究工作仍有哪些不足？02 这篇论文主要解决了什么问题？03 这篇论文解决问题采用的关键解决方案是什么？04 这篇论文的主要贡献是什么&am…...

编程日记 2025/5/30 8:33:09

CoOAG：首个捕捉学术研究兴趣动态演变的数据集

2025-04-24，由西安交通大学基于学术合作网络构建一种新的动态图数据集CoOAG，用于研究动态图中的节点分类问题。该数据集通过捕捉作者研究兴趣的动态变化，为动态图学习领域提供了新的研究方向和测试平台，特别是在标签受限的动态节点…...

编程日记 2025/6/1 9:11:24

决策树随机深林

决策树和随机森林是机器学习中常用的两种模型，以下是对它们的简单介绍： 决策树 - 原理：通过一系列的条件判断对样本进行分类或预测。它由节点（内部节点是属性上的测试，叶节点是类别或值）和边组成&#xff0…...

编程日记 2025/5/25 11:41:55

Unity 和 Unreal Engine（UE）两大主流游戏引擎的核心使用方法

以下是 Unity 和 Unreal Engine（UE） 两大主流游戏引擎的核心使用方法和对比分析，帮助开发者快速上手并根据项目需求选择合适工具： 一、Unity 使用指南 1. 安装与配置安装：从 Unity Hub 下载，选择长期支持…...

编程日记 2025/5/26 6:06:07

Maven 依赖范围（Scope）详解

Maven 依赖范围（Scope）详解 Maven 是一个强大的项目管理工具，广泛用于 Java 开发中构建、管理和部署应用程序。在使用 Maven 构建项目时，我们经常需要引入各种第三方库或框架作为项目的依赖项。通过在 pom.xml 文件中的 <depe…...

编程日记 2025/5/28 18:06:07

博物馆除湿控湿保卫战：M-5J1R 电解除湿科技如何重塑文物守护的未来

在卢浮宫幽深的长廊里，达芬奇的《蒙娜丽莎》正经历着一场看不见的战争——不是来自时间的侵蚀，而是空气中无形的水分子。每一件文物都在与湿度进行着无声的抗争，这场抗争关乎人类文明的延续。湿度，这个看不见的文物杀手&#xff0…...

编程日记 2025/5/19 3:59:34

消防应急物资智能调用立库：豪越科技助力消防“速战速决”

在消防救援的战场上，时间就是生命，每一秒都关乎着人民群众的生命财产安全。然而，在过去的紧急救援中，应急物资无法及时到位的情况时有发生，成为制约救援效率的关键难题，给救援工作带来了巨大的困境。想象一…...

编程日记 2025/5/24 16:36:07

机器学习基础理论 - 分类问题评估指标

几个定义：混淆矩阵 TP： True Positives，表示实际为正例且被分类器判定为正例的样本数FP： False Positives，表示实际为负例且被分类器判定为正例的样本数FN： False Negatives，表示实际为正例但被分类器判定为负例的样本数TN： True Negatives，表示实际为负例且被分类…...

编程日记 2025/5/29 9:25:15

深度学习4.1 多层感知机

基本概念多层感知机（Multilayer Perceptron, MLP）是一种‌前馈人工神经网络‌，由输入层、至少一个隐藏层和输出层组成。 ‌核心特点‌： 采用‌全连接结构‌（相邻层神经元全部相连； 通过‌非线性激活函数‌…...

编程日记 2025/5/28 7:35:53

解决两个技术问题后小有感触－QZ Tray使用经验小总结

老朋友都知道，我现在是一家软件公司销售部门的项目经理和全栈开发工程师，就是这么“奇怪”的岗位，大概我是公司销售团队里比较少有技术背景、销售业绩又不那么理想的销售。近期在某个票务系统项目上驻场，原来我是这个项目的项目…...

编程日记 2025/5/31 8:26:34

非计算机专业如何利用AI开展跨学科和交叉研究

对于非计算机专业的研究者，利用AI开展跨学科研究既充满机遇也面临挑战。以下是一份系统化的指南，帮助您高效入门并找到交叉研究的突破口： 一、认知重塑：理解AI的本质与局限 AI不是“黑箱”：现代AI以数据驱动为核心&a…...

编程日记 2025/5/29 19:06:48

Python 数据可视化进阶：精准插入图表到指定 Excel 工作表

Python 数据可视化进阶：精准插入图表到指定 Excel 工作表在处理数据的过程中，我们常常需要将生成的图表精准地插入到已存在数据的 Excel 文件的指定工作表中。借助 Python 的强大库组合，这一操作得以高效实现。以下是经过优化和注释补充的代…...

编程日记 2025/6/4 16:45:44

MQTT - MQTT 实践（Windows EMQX、MQTTX、客户端认证、连接与主题）

概述 -说明概括MQTT消息队列遥测传输协议一种规则EMQX一款大规模分布式物联网接入平台一个平台MQTTXMQTT 客户端一个工具工具（MQTTX）和平台（EMQX）间遵循规则（MQTT）即可进行双向通信一、Windows EMQX 下…...

编程日记 2025/6/3 7:10:03

【计算机网络物理层】从信号传输到介质选型的核心技术解析

目录前言技术背景与价值当前技术痛点解决方案概述目标读者说明一、技术原理剖析核心概念图解核心作用讲解关键技术模块说明技术选型对比二、实战演示环境配置要求核心代码实现（信号模拟）运行结果验证三、性能对比测试方法论量化数据对比结果分析四、…...

编程日记 2025/5/31 9:12:37

云原生--核心组件-容器篇-5-Docker核心之-容器

1、Docker容器的定义与核心概念定义： Docker容器是基于Docker镜像运行的轻量级、独立、可移植的运行环境，它封装了应用程序及其依赖项，提供了一个隔离的执行空间。容器化应用比传统的虚拟机更加高效，因为它们共享主机操作系统的内…...

编程日记 2025/6/4 17:15:09

一、I/O的相关概念

I/O的相关概念 1、I/O I/O即Input和Output，用户进程执行I/O操作，归结起来，也就是向操作系统发出请求，读请求就把数据填到缓冲区里，写数据就把缓冲区里数据排干，目的地可以是磁盘也可以是其他通道。进程通…...

编程日记 2025/5/26 8:05:59

django filter 日期大于当前日期的

在Django中，如果你想要过滤出日期大于当前日期的记录，你可以使用Django的QuerySet API中的__gt（大于）操作符。这里是如何做到这一点的步骤： 确定你的模型：首先，确保你有一个模型（Mo…...

编程日记 2025/5/28 14:25:32

Unreal Engine 实现智慧水库周边环境以及智慧社区模拟的实例

下面分别为你介绍使用 Unreal Engine 实现智慧水库周边环境以及智慧社区模拟的实例。智慧水库周边环境模拟 1. 场景搭建地形与地理特征：利用 Unreal Engine 的地形编辑工具，依据水库实际的地理测绘数据构建地形。模拟山脉、丘陵、河流等周边地貌&am…...

编程日记 2025/6/4 17:51:06

[MCU]SRAM

MCU存储体系 1.SRAM 2.FLASH 3.TCM SRAM SRAM（Static Random-Access Memory）:静态随机存取存储器. 特点：访问速度快、断电丢失、不 SRAM分类 1.系统SRAM：连接在系统总线上，所有外设和CPU都可访问 2.TCM SRAM&…...

编程日记 2025/5/26 10:54:44

【dockerredis】用docker容器运行单机redis

一、实验环境操作系统：CentOS7.5 Minimal docker版本：18.06-ce redis版本：6.0.6 二、安装docker 关闭selinux # setenforce 0 # sed -i s/^SELINUX.*/SELINUXpermissive/g /etc/selinux/config 下载docker二进制安装包 # yum -y install…...

编程日记 2025/5/27 6:04:40

游戏引擎学习第247天:简化DEBUG_VALUE

欢迎。关于纹理传输的详细情况。上周我们刚刚完成了纹理下载的相关工作，但实际上并没有完全解决这个问题。问题的核心是，当前关于纹理下载的正确方式仍然存在较大的不确定性。尽管我们在进行纹理下载的工作时已有一定进展，但依旧有不少模糊…...

编程日记 2025/6/1 20:52:27

Super Sample Tasker 学习-1

一、Super-Simple Tasker (SST) 是一个基于事件的、抢占式的、优先级基础的实时操作系统（RTOS）内核，完全符合 Rate Monotonic Analysis/Scheduling (RMA/RMS) 的要求。此STT RTOS主要分成两大类，分别是抢占式SST和非抢占式STT0&…...

编程日记 2025/5/20 8:58:19

【C++】类和对象【中上】

目录一、类与对象1、构造函数2、析构函数3、拷贝构造函数个人主页<—请点击 C专栏<—请点击一、类与对象默认成员函数就是用户没有显式实现，编译器会自动生成的成员函数称为默认成员函数。⼀个类，我们不写的情况下编译器会默认生成以下6个默…...

编程日记 2025/5/26 10:00:47

概率论与统计（不确定性分析）主要应用在什么方面？涉及到具体知识是什么？

用户问的是概率论与统计（不确定性分析）的主要应用方面，涉及的具体知识以及具体公式。首先，我需要确定概率论与统计在哪些领域有应用，比如工程、金融、医学、数据科学等等。然后，具体知识部分应该包括概率论…...

编程日记 2025/5/20 11:50:57

java面向对象编程【高级篇】之多态

目录 🚀前言🤔什么是多态？🌟多态的优缺点💯优点💯缺点 🌟类型转换💯自动类型转换💯强制类型转换 🚀前言大家好！我是 EnigmaCoder。本文介绍java…...

编程日记 2025/5/29 10:16:09

低压电工常见知识点

一.工厂用电 1.工厂一般有电源380V和220V。三相:黄绿红蓝双色助记符:王力宏分别对应第一相(R),第二相(S)，第三相(T)，零线(N),地线(PE) 单相:红黑对应火线(L) 零线(N) 左零右火二.人体安全电压是36V 三.变压器的讲解变压器的符号…...

编程日记 2025/5/29 14:55:10

【Android】硬件合成器 HWC

硬件合成器(HWC) 深度解析一、HWC 基本概念硬件合成器(Hardware Composer, HWC)是Android显示系统的核心组件，负责高效管理图形层的合成与显示。作为SurfaceFlinger的关键模块，HWC通过硬件加速实现图层合成，显著提升性能并降低功耗。二…...

编程日记 2025/5/29 8:46:50

【Android】dialogX对话框框架

文章目录 DialogX一、引入二、基础对话框 MessageDialog 和输入对话框 InputDialog2.1.0 显示一个简单对话框2.1.1 构造对话框2.1.2 按钮点击回调2.2 输入对话框按钮点击回调2.3自定义布局2.4自定义进入和关闭动画三、等待框WaitDialog和提示框TipDialog3.1 等待框3.2 提示框…...

编程日记 2025/5/29 14:52:11

代码优化建议

相关文章：