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

[loj#115] 无源汇有上下界可行流 网络流

#115. 无源汇有上下界可行流

内存限制:256 MiB时间限制:1000 ms标准输入输出
题目类型:传统评测方式:Special Judge
上传者: 匿名
提交 提交记录 统计 讨论 测试数据
 

题目描述

这是一道模板题。

n nn 个点,m mm 条边,每条边 e ee 有一个流量下界 lower(e) \text{lower}(e)lower(e) 和流量上界 upper(e) \text{upper}(e)upper(e),求一种可行方案使得在所有点满足流量平衡条件的前提下,所有边满足流量限制。

输入格式

第一行两个正整数 n nn、m mm。

之后的 m mm 行,每行四个整数 s ss、t tt、lower \text{lower}lower、upper \text{upper}upper。

输出格式

如果无解,输出一行 NO

否则第一行输出 YES,之后 m mm 行每行一个整数,表示每条边的流量。

样例

样例输入 1

4 6
1 2 1 2
2 3 1 2
3 4 1 2
4 1 1 2
1 3 1 2
4 2 1 2

样例输出 1

NO

样例输入 2

4 6
1 2 1 3
2 3 1 3
3 4 1 3
4 1 1 3
1 3 1 3
4 2 1 3

样例输出 2

YES
1
2
3
2
1
1

数据范围与提示

1≤n≤200,1≤m≤10200 1 \leq n \leq 200, 1 \leq m \leq 102001n200,1m10200

 

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<cstdlib>
 5 #include<cmath>
 6 #include<algorithm>
 7 #define maxm 12000
 8 #define maxn 500
 9 using namespace std;
10 int read() {
11     int x=0,f=1;char ch=getchar();
12     while(!isdigit(ch)){ch=getchar();}
13     while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
14     return x;
15 }
16 struct data {
17     int to,next,w,f;
18 }e[maxm*16];
19 int head[maxn],cnt;
20 int cur[maxn];
21 void add(int u,int v,int w,int f){e[cnt].next=head[u];e[cnt].to=v;e[cnt].w=w;e[cnt].f=f;head[u]=cnt++;}
22 int n,m,s,t;
23 int q[maxn];
24 bool vis[maxn];
25 int dis[maxn];
26 bool bfs() {
27     memset(dis,-97,sizeof(dis));
28     int h=0,tt=1;
29     q[h]=t;
30     vis[t]=1;
31     dis[t]=0;
32     while(h!=tt) {
33         int now=q[h];h++;vis[now]=0;if(h==maxn) h=0;
34         for(int i=head[now];i>=0;i=e[i].next) {
35             int to=e[i].to;
36             if(e[i^1].w&&dis[to]<-1000000) {
37                 dis[to]=dis[now]-1;
38                 if(!vis[to]){
39                     vis[to]=1;
40                     q[tt++]=to;if(tt==maxn) tt=0;
41                 }
42             }
43         }
44     }
45     return dis[s]>=-1000000;
46 }
47 int dfs(int now,int a) {
48     if(now==t||a==0) return a;
49     int flow=0,f;
50     for(int i=cur[now];i>=0;i=e[i].next) {
51         int to=e[i].to;
52         if(dis[to]==dis[now]+1&&e[i].w>0&&(f=dfs(to,min(a,e[i].w)))) {
53             e[i].w-=f;
54             e[i^1].w+=f;
55             flow+=f;
56             a-=f;
57             if(a==0) return flow;
58         }
59         cur[now]=i;
60     }
61     if(!flow) dis[now]=-1;
62     return flow;
63 }
64 int main() {
65     memset(head,-1,sizeof(head));
66     n=read(),m=read(),s=0,t=n+1;
67     int tot=0;
68     for(int i=1;i<=m;i++) {
69         int u=read(),v=read(),lw=read(),w=read();
70         tot+=lw;
71         add(u,v,w-lw,w);add(v,u,0,0);
72         add(0,v,lw,lw);add(v,0,0,lw);
73         add(u,n+1,lw,lw);add(n+1,u,0,0);
74     }
75     int ans=0;
76     while(bfs()){
77         for(int i=0;i<=n+1;i++) cur[i]=head[i];
78         ans+=dfs(s,2147483647);
79     }
80     if(ans==tot) {
81         printf("YES\n");
82         for(int i=0;i<m*6;i+=6) {printf("%d\n",e[i].f-e[i].w);}
83         return 0;
84     }
85     printf("NO\n");
86 }
View Code

 

转载于:https://www.cnblogs.com/wls001/p/7867630.html

相关文章:

  • php程序设计形成性手册,PHP动态网站设计(专,2020春)形成性考核_第6章 单元测试0...
  • linux命令行动态输出,Linux top实时显示process的动态命令详解
  • 我的cheatsheet
  • linux文件赋予用户权限,Linux 给用户赋予操作权限
  • Ubuntu 16.04安装JAD反编译工具(Java)
  • 查询linux命令位置,查看登录过Linux的IP的地理位置(基于last命令)
  • [poj] 3974 Palindrome
  • linux遍历目录删除指定文件,shell脚本删除目录下的指定文件
  • 【转】VC++计算当前时间点间隔N天的时间(不使用CTimeSpan类)
  • linux下新建shell命令接口,Linux Shell(脚本)编程入门
  • Ubuntu下搭建基于apache2的gerrit+gitweb服务器
  • Linux每个用户单独配置ssh,linux – 每个用户的SSH MOTD
  • linux针对内存uce隔离内存,Linux运维知识之在linux系统中,iomem_resource的信息被输出到/proc/iomem中...
  • intellij IDEA里各图标对应的文件类型
  • linux目录中grid,用MongoDB基于GridFS存储文件
  • 【vuex入门系列02】mutation接收单个参数和多个参数
  • 【跃迁之路】【641天】程序员高效学习方法论探索系列(实验阶段398-2018.11.14)...
  • C++类中的特殊成员函数
  • HTTP中的ETag在移动客户端的应用
  • open-falcon 开发笔记(一):从零开始搭建虚拟服务器和监测环境
  • React 快速上手 - 06 容器组件、展示组件、操作组件
  • 前端知识点整理(待续)
  • 浅谈Golang中select的用法
  • 区块链将重新定义世界
  • 如何设计一个比特币钱包服务
  • 数组大概知多少
  • 限制Java线程池运行线程以及等待线程数量的策略
  • 教程:使用iPhone相机和openCV来完成3D重建(第一部分) ...
  • # 数据结构
  • (1)Map集合 (2)异常机制 (3)File类 (4)I/O流
  • (23)Linux的软硬连接
  • (39)STM32——FLASH闪存
  • (二)c52学习之旅-简单了解单片机
  • (二)hibernate配置管理
  • (简单) HDU 2612 Find a way,BFS。
  • (使用vite搭建vue3项目(vite + vue3 + vue router + pinia + element plus))
  • (转)创业家杂志:UCWEB天使第一步
  • .NET 2.0中新增的一些TryGet,TryParse等方法
  • .net core 调用c dll_用C++生成一个简单的DLL文件VS2008
  • .NET开源项目介绍及资源推荐:数据持久层 (微软MVP写作)
  • @ConfigurationProperties注解对数据的自动封装
  • @GetMapping和@RequestMapping的区别
  • @WebService和@WebMethod注解的用法
  • [ C++ ] STL---string类的模拟实现
  • [《百万宝贝》观后]To be or not to be?
  • [2019/05/17]解决springboot测试List接口时JSON传参异常
  • [8481302]博弈论 斯坦福game theory stanford week 1
  • [ACL2022] Text Smoothing: 一种在文本分类任务上的数据增强方法
  • [AutoSar]BSW_Com07 CAN报文接收流程的函数调用
  • [iOS]iOS获取设备信息经常用法
  • [ios-必看] IOS调试技巧:当程序崩溃的时候怎么办 iphone IOS
  • [Java开发之路](14)反射机制
  • [JS入门到进阶] 7条关于 async await 的使用口诀,新学 async await?背10遍,以后要考!快收藏
  • [linux]--关于进程概念(上)
  • [Oh My C++ Diary]善用三目运算符(a?b:c)