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

上下界网络流基础

eb211a7b0850ad5ea674f10727eb59a9
/*
Dinic无源汇上下界可行流
剩下几个板子先咕了下期补
*/
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,s,t,tot=1,maxflow,dis[100010],now[100010],V[100010],flow;
int hed[100010],ver[100010],nxt[100010],edg[100010],ppp[100010];
void add(int a,int b,int c){ver[++tot]=b,nxt[tot]=hed[a],hed[a]=tot,edg[tot]=c;ver[++tot]=a,nxt[tot]=hed[b],hed[b]=tot,edg[tot]=0;
}bool bfs(){queue<int>q;memset(dis,0,sizeof(dis));dis[s]=1;now[s]=hed[s];q.push(s);while(!q.empty()){int u=q.front();q.pop();for(int i=hed[u];i;i=nxt[i]){int v=ver[i];if(dis[v]||(!edg[i])){continue;}now[v]=hed[v];dis[v]=dis[u]+1;q.push(v);if(v==t){return 1;}}}return 0;
}
int dinic(int u,int flow){if(u==t){return flow;}int i,rest=flow;for(i=now[u];i&&rest;i=nxt[i]){int v=ver[i];if(dis[v]!=dis[u]+1||(!edg[i])){continue;}int k=dinic(v,min(rest,edg[i]));if(!k){dis[v]=0;	}edg[i]-=k;edg[i^1]+=k;rest-=k;}now[u]=i;return flow-rest;
}
signed main(){cin>>n>>m;s=0,t=n+1;for(int i=1;i<=m;i++){int u,v,p,q;cin>>u>>v>>p>>q;add(u,v,q-p);V[u]-=p,V[v]+=p;ppp[i]=p;}int sum=0;for(int i=1;i<=n;i++){if(V[i]>0){add(s,i,V[i]);sum+=V[i];}if(V[i]<0){add(i,t,-V[i]);}}while(bfs()){while(flow=dinic(s,1e18)){maxflow+=flow;}}if(maxflow<sum){cout<<"No";return 0;}cout<<"Yes\n";for(int i=3;i<=2*m+1;i+=2){cout<<edg[i]+ppp[i/2]<<endl;}return 0;
}

  

 

http://www.jsqmd.com/news/330855/

相关文章:

  • 开题报告被批 “逻辑悬浮”?虎贲等考 AI 让研究从 “空想” 到 “落地”,导师直接点头
  • Linux综合性能监控工具dstat命令详解
  • 如果RSA不在安全,咋办呢?
  • Linux Screen 命令入门指南
  • 开题报告 基于SSM“爱的小窝”家庭管理网站
  • 开题报告 基于大数据的学生综合评价系统
  • 开题报告 基于Java的企业人事智能推荐系统
  • 【人工智能学习-AI入试相关题目练习-第十六次】
  • C语言:2026.1.30(位段,联合体)
  • 贾子公理体系(Kucius Axiomatic System v1.0)深度剖析:从底层逻辑到跨域统治力
  • 位置服务的城市路线分享系统任务书
  • 开题报告 基于JAVA多客户端的“动漫日记”网站的设计与实现
  • 基于深度学习和SVM的印度车牌字符识别方法 外文翻译
  • Python判断MySQL表是否存在,不存在则创建
  • 开题报告 企业办公物品管理系统设计与实现
  • Vue 中如何修改地址栏参数并重新加载?
  • MCP——AI连接现实世界的“标准接口”
  • 开题报告 健身房会员管理系统的设计与实现
  • 开题报告 基于Android的移动点餐系统
  • MySQL删除表语句详解
  • 企业AI生态迭代优化的6个步骤:AI应用架构师总结的实战经验
  • 小程序 购物商城开题报告
  • 《速看!提示工程架构师带你探索提示工程在新兴技术的应用奥秘》
  • 考试必备
  • 协同过滤算法的微博爬虫系统
  • 小学数学口算题卡自动生成系统
  • 开题报告 独立学院毕业生就业管理信息系统的设计与实现
  • 计网——物理层
  • 开题报告 电子病历系统的设计与实现
  • 《速通秘籍!AI应用架构师利用AI驱动价值创造的有效途径》