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

网络流 费用流 EK算法

image

模板题:洛谷p3381

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+10,M=5e4+10,INF=0x3f3f3f3f;
typedef long long LL;
int n,m,s,t,id=1;
int e[M<<1],h[N],cap[M<<1],d[M<<1],ne[M<<1];
int dp[N],vis[N],mf[N],pre[N];
void add(int u,int v,int w,int c){id++;e[id]=v;cap[id]=w;d[id]=c;ne[id]=h[u];h[u]=id;
}bool spfa(){memset(dp,0x3f,sizeof(dp));memset(mf,0,sizeof(mf));queue<int> q;q.push(s);vis[s]=1;dp[s]=0;mf[s]=INF;while(q.size()){int u=q.front();q.pop();vis[u]=0;for(int i=h[u];i;i=ne[i]){int v=e[i],w=d[i],c=cap[i];if(dp[v]>dp[u]+w&&c){dp[v]=dp[u]+w;mf[v]=min(mf[u],c);pre[v]=i;if(!vis[v]){q.push(v);vis[v]=1;}}}}return mf[t]>0;
}void EK(){LL flow=0,cost=0;while(spfa()){for(int v=t;v!=s;){int i=pre[v];cap[i]-=mf[t];cap[i^1]+=mf[t];v=e[i^1];}flow+=mf[t];cost+=mf[t]*dp[t];}cout<<flow<<' '<<cost<<endl;
}int main(){cin.tie(nullptr)->sync_with_stdio(false);cin>>n>>m>>s>>t;for(int i=1;i<=m;i++){int u,v,w,c;cin>>u>>v>>w>>c;add(u,v,w,c);add(v,u,0,-c);}EK();return 0;
}
http://www.hskmm.com/?act=detail&tid=23563

相关文章:

  • “AI元人文”构想说明:构建智能时代的人文学科新范式
  • 双向LSTM-Attention模型
  • Xilinx高性能NVMe Host控制器IP+PCIe 3.0软核控制器IP,4通道DMA,1通道IO,纯逻辑实现,AXI4和AXI4-Stream DMA接口,支持PCIe 3.0和4.0
  • 公私合作抗击网络威胁的创新实践
  • 特征工程
  • 一些dp题
  • 【人工智能通识专栏】第三十二讲:本地化部署模型 - 教程
  • [Node.js] chokidar 文件系统监听库
  • Jenkins安装并与GitLab集成,实现dev、qa、uat、prod多分支持续集成的详细步骤 - 指南
  • ZR 2025 十一集训 #1
  • Channel-Driven 降低模块耦合设计复杂度
  • how to download a websites favicon.ico
  • mini-spring实现
  • 10.3
  • Linux 代码利用 STDOUT 打印日志导致应用“假死”?一次线上 Bug 的深度排查与解决
  • 2025 年地坪研磨机公司推荐榜单:盘点 TOP 品牌的格力,宁德时代等标杆客户合作案例
  • Python 新手入门:从零开始学习 Python 的 10 个关键步骤
  • EPL S22 Stage 2 赛前前瞻
  • 计算机类毕业设计开题报告注意事项 - 教程
  • 2025山东设备回收公司 TOP 交易服务推荐排行榜,济宁,梁山设备回收,二手,饮料,食品,制药,实验室,生产线,化工厂,废旧,大型,专业设备回收公司推荐
  • 2025饮料设备回收公司 TOP 交易服务推荐排行榜,济宁,梁山饮料设备回收果汁饮料整厂,饮料生产线,碳酸饮料,乳制品,杀菌机,果汁饮料,二手灌装机,果汁设备回收公司推荐
  • 压力位和支撑位概念
  • 2025 年浙江义乌匹克球拍厂家 TOP 企业品牌推荐排行榜,碳纤维,高级,轻质,定制,高定,比赛专用,玻璃纤维,木制,儿童,匹克球拍套装公司推荐
  • 实用指南:k8s中的schedule
  • 【光照】[PBR][环境光]实现方法解析
  • 树莓派搭建NAS之五:数据同步
  • 初识文件管理
  • 微信社群机器人搭建 教程/开发
  • 2025 年激光粒度仪厂家 TOP 企业品牌推荐排行榜,电位仪 / 纳米粒度及 Zeta 电位仪 / Zeta 电位仪公司推荐
  • 微信智能机器人开发-基于WTAPI框架,实现强大的个微管理