#网络流,费用流,SLF优化,SPFA,zkw费用流#jzoj 1586 codevs 1362 洛谷 2604 网络扩容

2024-02-11 05:58

本文主要是介绍#网络流,费用流,SLF优化,SPFA,zkw费用流#jzoj 1586 codevs 1362 洛谷 2604 网络扩容,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目

有两个问题,首先求1到 n n n的最大流(不解释了),然后求1到n使最大流扩展 k k k的费用,每扩展一个最大流,扩展一次边的费用


分析

当然如何做第二个问题,可以重新建一个汇点流量是最大流 + k +k +k,费用为0,并且原来的边再建一次从 u u u v v v,费用为该边的费用,流量无限跑一次最大流,then就讲完了


代码

    #include <cstdio>#include <cstring>#include <queue>#define rr registerusing namespace std;struct node{int y,w,f,next;}e[20005];int n,k=1,dis[1003],ls[1003],ans; bool v[1003];inline int in(){rr int ans=0; rr char c=getchar();while (c<48||c>57) c=getchar();while (c>47&&c<58) ans=(ans<<3)+(ans<<1)+c-48,c=getchar();return ans;}inline void add(int x,int y,int w,int f){e[++k]=(node){y,w,f,ls[x]}; ls[x]=k;e[++k]=(node){x,0,-f,ls[y]}; ls[y]=k;}inline int spfa(){//反向跑spfamemset(v,0,sizeof(v)); memset(dis,127/3,sizeof(dis));dis[n]=0; v[n]=1; rr deque<int>q; q.push_back(n);while (q.size()){rr int x=q.front(); q.pop_front();for (rr int i=ls[x];i;i=e[i].next)if (e[i^1].w&&dis[e[i].y]>dis[x]-e[i].f){dis[e[i].y]=dis[x]-e[i].f;if (!v[e[i].y]){v[e[i].y]=1;if (q.size()&&dis[e[i].y]<dis[q.front()]) q.push_front(e[i].y); else q.push_back(e[i].y);}}v[x]=0;}return dis[n+1]<707406378;}inline int dfs(int x,int now){//长得很像dinicif (x==n) {v[n]=1; return now;}rr int rest=0,f; v[x]=1;for (rr int i=ls[x];i;i=e[i].next)if (!v[e[i].y]&&e[i].w>0&&dis[e[i].y]+e[i].f==dis[x]){rest+=(f=dfs(e[i].y,min(e[i].w,now-rest)));if (f) ans+=e[i].f*f,e[i].w-=f,e[i^1].w+=f;if (now==rest) return now;}return rest;}inline int zkw(){int ans=0;while (spfa()){do{memset(v,0,sizeof(v));ans+=dfs(n+1,1e9);}while (v[n]);}return ans;}int main(){n=in(); rr int m=in(),t=in();rr int w[m+1],f[m+1],t1;for (rr int i=1;i<=m;i++){rr int x=in(),y=in();w[i]=in(); f[i]=in();add(x,y,w[i],0);}add(n+1,1,2333333,0);printf("%d ",t1=zkw()); t+=t1;e[k].w=0; e[k^1].w=t;//超级源点for (rr int i=1;i<=m;i++) e[i<<1].w=w[i],e[i<<1|1].w=0;//重新建图for (rr int i=1;i<=m;i++) add(e[i<<1|1].y,e[i<<1].y,23333333,f[i]);//无限流量zkw(); return !printf("%d",ans);}

这篇关于#网络流,费用流,SLF优化,SPFA,zkw费用流#jzoj 1586 codevs 1362 洛谷 2604 网络扩容的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/698994

相关文章

python如何下载网络文件到本地指定文件夹

《python如何下载网络文件到本地指定文件夹》这篇文章主要为大家详细介绍了python如何实现下载网络文件到本地指定文件夹,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下...  在python中下载文件到本地指定文件夹可以通过以下步骤实现,使用requests库处理HTTP请求,并结合o

SpringBoot中HTTP连接池的配置与优化

《SpringBoot中HTTP连接池的配置与优化》这篇文章主要为大家详细介绍了SpringBoot中HTTP连接池的配置与优化的相关知识,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一... 目录一、HTTP连接池的核心价值二、Spring Boot集成方案方案1:Apache HttpCl

PyTorch高级特性与性能优化方式

《PyTorch高级特性与性能优化方式》:本文主要介绍PyTorch高级特性与性能优化方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、自动化机制1.自动微分机制2.动态计算图二、性能优化1.内存管理2.GPU加速3.多GPU训练三、分布式训练1.分布式数据

MySQL中like模糊查询的优化方案

《MySQL中like模糊查询的优化方案》在MySQL中,like模糊查询是一种常用的查询方式,但在某些情况下可能会导致性能问题,本文将介绍八种优化MySQL中like模糊查询的方法,需要的朋友可以参... 目录1. 避免以通配符开头的查询2. 使用全文索引(Full-text Index)3. 使用前缀索

Linux高并发场景下的网络参数调优实战指南

《Linux高并发场景下的网络参数调优实战指南》在高并发网络服务场景中,Linux内核的默认网络参数往往无法满足需求,导致性能瓶颈、连接超时甚至服务崩溃,本文基于真实案例分析,从参数解读、问题诊断到优... 目录一、问题背景:当并发连接遇上性能瓶颈1.1 案例环境1.2 初始参数分析二、深度诊断:连接状态与

C#实现高性能Excel百万数据导出优化实战指南

《C#实现高性能Excel百万数据导出优化实战指南》在日常工作中,Excel数据导出是一个常见的需求,然而,当数据量较大时,性能和内存问题往往会成为限制导出效率的瓶颈,下面我们看看C#如何结合EPPl... 目录一、技术方案核心对比二、各方案选型建议三、性能对比数据四、核心代码实现1. MiniExcel

Qt实现网络数据解析的方法总结

《Qt实现网络数据解析的方法总结》在Qt中解析网络数据通常涉及接收原始字节流,并将其转换为有意义的应用层数据,这篇文章为大家介绍了详细步骤和示例,感兴趣的小伙伴可以了解下... 目录1. 网络数据接收2. 缓冲区管理(处理粘包/拆包)3. 常见数据格式解析3.1 jsON解析3.2 XML解析3.3 自定义

MySQL索引的优化之LIKE模糊查询功能实现

《MySQL索引的优化之LIKE模糊查询功能实现》:本文主要介绍MySQL索引的优化之LIKE模糊查询功能实现,本文通过示例代码给大家介绍的非常详细,感兴趣的朋友一起看看吧... 目录一、前缀匹配优化二、后缀匹配优化三、中间匹配优化四、覆盖索引优化五、减少查询范围六、避免通配符开头七、使用外部搜索引擎八、分

Python通过模块化开发优化代码的技巧分享

《Python通过模块化开发优化代码的技巧分享》模块化开发就是把代码拆成一个个“零件”,该封装封装,该拆分拆分,下面小编就来和大家简单聊聊python如何用模块化开发进行代码优化吧... 目录什么是模块化开发如何拆分代码改进版:拆分成模块让模块更强大:使用 __init__.py你一定会遇到的问题模www.

SpringBoot首笔交易慢问题排查与优化方案

《SpringBoot首笔交易慢问题排查与优化方案》在我们的微服务项目中,遇到这样的问题:应用启动后,第一笔交易响应耗时高达4、5秒,而后续请求均能在毫秒级完成,这不仅触发监控告警,也极大影响了用户体... 目录问题背景排查步骤1. 日志分析2. 性能工具定位优化方案:提前预热各种资源1. Flowable