当前位置: 首页 > 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装双系统…...

Linux应用开发之网络套接字编程(实例篇)

服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

ArcGIS Pro制作水平横向图例+多级标注

今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作&#xff1a;ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等&#xff08;ArcGIS出图图例8大技巧&#xff09;&#xff0c;那这次我们看看ArcGIS Pro如何更加快捷的操作。…...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...

JS手写代码篇----使用Promise封装AJAX请求

15、使用Promise封装AJAX请求 promise就有reject和resolve了&#xff0c;就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...

Redis:现代应用开发的高效内存数据存储利器

一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发&#xff0c;其初衷是为了满足他自己的一个项目需求&#xff0c;即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源&#xff0c;Redis凭借其简单易用、…...

免费数学几何作图web平台

光锐软件免费数学工具&#xff0c;maths,数学制图&#xff0c;数学作图&#xff0c;几何作图&#xff0c;几何&#xff0c;AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...

怎么让Comfyui导出的图像不包含工作流信息,

为了数据安全&#xff0c;让Comfyui导出的图像不包含工作流信息&#xff0c;导出的图像就不会拖到comfyui中加载出来工作流。 ComfyUI的目录下node.py 直接移除 pnginfo&#xff08;推荐&#xff09;​​ 在 save_images 方法中&#xff0c;​​删除或注释掉所有与 metadata …...