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

最大流笔记

概念

求两点间的路径中可在同一时间内通过的最大量

EK算法

通过bfs找通路,找到后回溯;

每确定一条边时,同时建立一天反方向的边以用来进行反悔操作(毕竟一次性找到正确方案的概率太低了)

code

#include<bits/stdc++.h>
#define ll long long
#define inl inline
#define re register
using namespace std;
inl int read() {int sum=0,f=1;char c=getchar();while(!isdigit(c)) {if(c=='-') f=-1;c=getchar();}while(isdigit(c)) {sum=(sum<<3)+(sum<<1)+(c^48);c=getchar();}return sum*f;
}
const int N=210;
int dis[10000010],ans,head[N<<1],tot=1,n,m,f[210][210];
struct node{int to,w,nxt;
}e[10000010];
inl void add(int u,int v,int w) {e[++tot].to=v;e[tot].w=w;e[tot].nxt=head[u];head[u]=tot;e[++tot].to=u;e[tot].w=0;e[tot].nxt=head[v];head[v]=tot;
}
bool vis[210];
int pre[N];
inl bool bfs() {memset(vis,0,sizeof(vis));queue<int> q;dis[1]=100000000;vis[1]=1;q.push(1);while(!q.empty()) {int u=q.front();q.pop();for(re int i=head[u];i;i=e[i].nxt) {int v=e[i].to;if(vis[v]==1 || e[i].w==0) continue;dis[v]=min(dis[u],e[i].w) ;//cout<<dis[v]<<endl;pre[v]=i;q.push(v);vis[v]=1;if(v==n) return 1;}}return 0;
}
inl void update() {int u=n;while(u!=1) {int v=pre[u] ;e[v].w-=dis[n];e[v^1].w+=dis[n];u=e[v^1].to;}ans+=dis[n];
}
int main() {m=read(),n=read();for(re int i=1;i<=m;i++) {int u=read(),v=read(),w=read();if(!f[u][v]) {add(u,v,w);f[u][v]=tot;}else{e[f[u][v]-1].w+=w;}}while(bfs()) {//cout<<dis[n]<<endl;update();}cout<<ans<<endl;return 0;
}

Dinic算法

也是运用bfs将原图进行分层,但统计答案时使用dfs,,可大大降低时间复杂度

code

#include<bits/stdc++.h>
#define ll long long
#define re register
#define inl inline
using namespace std;
inl int read() {int sum=0,f=1;char c=getchar();while(!isdigit(c)) {if(c=='-') f=-1;c=getchar();}while(isdigit(c)) {sum=(sum<<3)+(sum<<1)+(c^48);c=getchar();}return sum*f;
}
const int N=210;
int n,m,x,head[N<<1],f[210][210],tot=1,cur[N*N],ans,d[N];
struct node{int to,nxt,w;
}e[N*N+1000];
inl void add(int u,int v,int w) {//cout<<1<<endl;e[++tot].to=v;e[tot].w=w;e[tot].nxt=head[u];head[u]=tot;e[++tot].to=u;e[tot].w=0;e[tot].nxt=head[v];head[v]=tot;
}
inl bool bfs() {memset(d,0,sizeof(d));queue<int> q;d[1]=1;q.push(1);while(!q.empty()) {int u=q.front() ;q.pop();for(re int i=head[u];i;i=e[i].nxt) {int v=e[i].to;if(!d[v] && e[i].w) {d[v]=d[u]+1;q.push(v);if(v==n) return 1;}}}return 0;
}
inl int dfs(int u,int mf) {if(u==n) return mf;int tmp=0;for(int i=cur[u];i;i=e[i].nxt) {cur[u]=i;int v=e[i].to;if(d[v]==d[u]+1 && e[i].w) {int tmp1=dfs(v,min(mf,e[i].w));e[i].w-=tmp1;e[i^1].w+=tmp1;tmp+=tmp1;mf-=tmp1;if(!mf) break;}}if(!tmp) d[u]=0;return tmp;
}
inl void dinic() {while(bfs()) {memcpy(cur,head,sizeof head);ans+=dfs(1,100000000);}
}
int main() {n=read();m=read();x=read();//cout<<n<<" "<<m<<" "<<x<<endl;for(re int i=1;i<=m;i++) {int u=read(),v=read(),w=read();if(!f[u][v]) {add(u,v,w);f[u][v]=tot;}else{e[f[u][v]-1].w+=w;}}dinic();if(!ans) {puts("Orz Ni Jinan Saint Cow!");}else {int p=x/ans;if(p*ans<x) {p++;}printf("%d %d\n",ans,p);}return 0;
}

相关文章:

最大流笔记

概念 求两点间的路径中可在同一时间内通过的最大量 EK算法 通过bfs找通路&#xff0c;找到后回溯&#xff1b; 每确定一条边时&#xff0c;同时建立一天反方向的边以用来进行反悔操作&#xff08;毕竟一次性找到正确方案的概率太低了&#xff09; code #include<bits/st…...

el-tree父子不互相关联时,手动实现全选、反选、子级全选、清空功能

el-tree父子不互相关联时&#xff0c;手动实现全选、反选、子级全选、清空功能 1、功能实现图示 2、实现思路 当属性check-strictly为true时&#xff0c;父子节点不互相关联&#xff0c;如果需要全部选中或选择某一节点下的全部节点就必须手动选择每个节点&#xff0c;十分麻…...

模板与泛型编程笔记(一)入门篇

1. 推荐书籍 《C新经典 模板与泛型编程》难得的很容易看得懂的好书&#xff0c;作者讲技术不跳跃&#xff0c;娓娓道来&#xff0c;只要花点时间就能看懂。 2. 笔记 2.1 模板基础 模板为什么要用尖括号&#xff1f;因为便于编译器解析&#xff0c;可以将模板和普通函数声明…...

浅谈WebApi

一、基本介绍 Web API&#xff08;Web应用程序编程接口&#xff09;是一种用于构建应用程序的接口&#xff0c;它允许软件应用程序通过HTTP请求与Web服务器进行交互。Web API通常用于构建客户端-服务器应用程序&#xff0c;其中客户端可以是Web浏览器、移动应用程序、桌面应用程…...

9月14日,每日信息差

第一、宝马集团宣布对设计部门进行重组&#xff0c;并将于 2024 年 10 月 1 日成立一个跨品牌设计团队&#xff0c;由范・霍伊顿克领导。该团队将引入极星汽车设计主管马克西米利安・米索尼&#xff0c;负责宝马中高档和豪华车型以及宝马 Alpina 的设计工作。 第二、小鹏汇天飞…...

无人机控制与三维AI感知处理平台正式上线!

低空经济被誉为推动我国经济高质量发展的全新增长引擎&#xff0c;是一种以民用有人驾驶和无人驾驶航空器的各类低空飞行活动为牵引&#xff0c;辐射带动相关领域融合发展的综合性经济形态&#xff0c;2024年全国两会首次被纳入政府工作报告。 大势智慧积极响应国家低空经济政…...

9.11-kubeadm方式安装k8s

一、安装环境 编号主机名称ip地址1k8s-master192.168.2.662k8s-node01192.168.2.773k8s-node02192.168.2.88 二、前期准备 1.设置免密登录 [rootk8s-master ~]# ssh-keygen [rootk8s-master ~]# ssh-copy-id root192.168.2.77 [rootk8s-master ~]# ssh-copy-id root192.168…...

限流,流量整形算法

写在前面 源码 。 本文看下流量整形相关算法。 目前流量整形算法主要有三种&#xff0c;计数器&#xff0c;漏桶&#xff0c;令牌桶。分别看下咯&#xff01; 1&#xff1a;计数器 1.1&#xff1a;描述 单位时间内只允许指定数量的请求&#xff0c;如果是时间区间内超过指…...

【C++知识扫盲】------C++ 中的引用入门

在 C 中&#xff0c;引用&#xff08;reference&#xff09; 是一个非常重要的概念&#xff0c;它提供了一种别名机制&#xff0c;让我们可以给已经存在的变量起一个新的名字&#xff0c;并且能够通过这个别名直接操作原始变量。本文将详细介绍引用的定义、使用场景及其与指针的…...

【机器学习】6 ——最大熵模型

机器学习6——最大熵模型 目录 机器学习6——最大熵模型最大熵&#xff08;maximum entropy&#xff09;模型模型模型学习&#xff08;估计参数&#xff09;模型评价应用 最大熵&#xff08;maximum entropy&#xff09;模型 选择熵最大的概率模型 熵是衡量不确定性的&#xf…...

小程序——生命周期

文章目录 运行机制更新机制生命周期介绍应用级别生命周期页面级别生命周期组件生命周期生命周期两个细节补充说明总结 运行机制 用一张图简要概述一下小程序的运行机制 冷启动与热启动&#xff1a; 小程序启动可以分为两种情况&#xff0c;一种是冷启动&#xff0c;一种是热…...

基于微信小程序的宠物之家的设计与实现

作者&#xff1a;计算机学姐 开发技术&#xff1a;SpringBoot、SSM、Vue、MySQL、JSP、ElementUI等&#xff0c;“文末源码”。 专栏推荐&#xff1a;前后端分离项目源码、SpringBoot项目源码、SSM项目源码 系统展示 基于微信小程序JavaSpringBootVueMySQL的宠物之家/宠物综合…...

自定义EPICS在LabVIEW中的测试

继续上一篇&#xff1a;LabVIEW中EPICS客户端/服务端的测试 变量定义 You can use CaLabSoftIOC.vi to create new EPICS variables and start them. CA Lab - LabVIEW (Realtime) EPICS INPUT: PV set Cluster-array of names, data types and field definitions to crea…...

基于深度学习的农作物病害检测

基于深度学习的农作物病害检测利用卷积神经网络&#xff08;CNN&#xff09;、生成对抗网络&#xff08;GAN&#xff09;、Transformer等深度学习技术&#xff0c;自动识别和分类农作物的病害&#xff0c;帮助农业工作者提高作物管理效率、减少损失。 1. 农作物病害检测的挑战…...

【C#】命名规范

文章目录 C# 命名规范使用Pascal case使用Camel case方法、属性、类命名见名知义LINQ查询变量使用有意义的名称如何声明成员变量和字段正确格式化和缩进代码如何撰写备注 通用C#编码最佳实践如何将值与空字符串进行比较使用异常处理使用&&和||可获得更好的性能单一职责…...

超级帐本(Hyperledger)

1. Hyperledger 项目 Hyperledger 下有两类项目:第一类是区块链框架项目;第二类是支持这些区块链的相关工具或模块。 在 Hyperledger 框架下&#xff0c;目前有 5 个区块链框架项目&#xff1a;Fabric、Sawtooth Lake、Iroha、Burrow 和 Indy。 在模块类下&#xff0c;则有 Hyp…...

如何精细优化网站关键词排名:实战经验分享

在数字营销日益激烈的今天&#xff0c;我深知每一个关键词的排名都关乎着网站的流量与转化。凭借多年的实战经验&#xff0c;我深刻体会到&#xff0c;要想在浩如烟海的网络世界中脱颖而出&#xff0c;精细化的关键词优化策略至关重要。今天&#xff0c;我将从实战角度出发&…...

Ruoyi Cloud 本地启动

本文视频版本&#xff1a;https://www.bilibili.com/video/BV1SNtueBE9M 参考 http://doc.ruoyi.vip/ https://gitee.com/y_project/RuoYi-Cloud https://blog.csdn.net/cs_dnzk/article/details/135289966 https://doc.ruoyi.vip/ruoyi-cloud/cloud/seata.html#%E5%9F%BA%E6…...

Nginx解析:入门笔记

&#x1f308; 个人主页&#xff1a;danci_ &#x1f525; 系列专栏&#xff1a;《设计模式》《MYSQL》 &#x1f4aa;&#x1f3fb; 制定明确可量化的目标&#xff0c;坚持默默的做事。 ✨欢迎加入探索nginx之旅✨ &#x1f44b; 大家好&#xff01;文本学习和探索Nginx配置。…...

在 Mac 上安装双系统会影响性能吗,安装双系统会清除数据吗?

在 Mac 系统安装并使用双系统已经成为了许多用户办公的选择之一&#xff0c;双系统可以让用户在 Mac 上同时运行 Windows 或其他操作系统。然而&#xff0c;许多用户担心这样做会对 Mac 的性能产生影响。 接下来将给大家介绍 Mac 装双系统会影响性能吗&#xff0c;Mac装双系统…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

页面渲染流程与性能优化

页面渲染流程与性能优化详解&#xff08;完整版&#xff09; 一、现代浏览器渲染流程&#xff08;详细说明&#xff09; 1. 构建DOM树 浏览器接收到HTML文档后&#xff0c;会逐步解析并构建DOM&#xff08;Document Object Model&#xff09;树。具体过程如下&#xff1a; (…...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放

简介 前面两期文章我们介绍了I2S的读取和写入&#xff0c;一个是通过INMP441麦克风模块采集音频&#xff0c;一个是通过PCM5102A模块播放音频&#xff0c;那如果我们将两者结合起来&#xff0c;将麦克风采集到的音频通过PCM5102A播放&#xff0c;是不是就可以做一个扩音器了呢…...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中&#xff0c;新增了一个本地验证码接口 /code&#xff0c;使用函数式路由&#xff08;RouterFunction&#xff09;和 Hutool 的 Circle…...

安卓基础(aar)

重新设置java21的环境&#xff0c;临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的&#xff1a; MyApp/ ├── app/ …...

Netty从入门到进阶(二)

二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架&#xff0c;用于…...

在 Spring Boot 项目里,MYSQL中json类型字段使用

前言&#xff1a; 因为程序特殊需求导致&#xff0c;需要mysql数据库存储json类型数据&#xff0c;因此记录一下使用流程 1.java实体中新增字段 private List<User> users 2.增加mybatis-plus注解 TableField(typeHandler FastjsonTypeHandler.class) private Lis…...

深入浅出Diffusion模型:从原理到实践的全方位教程

I. 引言&#xff1a;生成式AI的黎明 – Diffusion模型是什么&#xff1f; 近年来&#xff0c;生成式人工智能&#xff08;Generative AI&#xff09;领域取得了爆炸性的进展&#xff0c;模型能够根据简单的文本提示创作出逼真的图像、连贯的文本&#xff0c;乃至更多令人惊叹的…...