LOJ #115. 无源汇有上下界可行流
2021/6/5 10:24:35
本文主要是介绍LOJ #115. 无源汇有上下界可行流,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
#115. 无源汇有上下界可行流描述
这是一道模板题。
n n n 个点,m m m 条边,每条边 e e e 有一个流量下界 lower(e) \text{lower}(e) lower(e) 和流量上界 upper(e) \text{upper}(e) upper(e),求一种可行方案使得在所有点满足流量平衡条件的前提下,所有边满足流量限制。
输入格式
第一行两个正整数 n n n、m m m。
之后的 m m m 行,每行四个整数 s s s、t t t、lower \text{lower} lower、upper \text{upper} upper。
输出格式
如果无解,输出一行 NO
。
否则第一行输出 YES
,之后 m m m 行每行一个整数,表示每条边的流量。
样例
样例输入 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 10200 1≤n≤200,1≤m≤10200
显示分类标签
板子题,就不细将了,有空整理一下。
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<queue> using namespace std; const int MAXN=2000001; inline char nc() { static char buf[MAXN],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++; } inline int read() { char c=nc();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=nc();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=nc();} return x*f; } int n,m,s,t; struct node { int u,v,flow,nxt; }edge[MAXN]; int head[MAXN],cur[MAXN],A[MAXN]; int num=0; void AddEdge(int x,int y,int z) { edge[num].u=x; edge[num].v=y; edge[num].flow=z; edge[num].nxt=head[x]; head[x]=num++; } void add_edge(int x,int y,int z) { AddEdge(x,y,z); AddEdge(y,x,0); } int deep[MAXN],L[MAXN]; bool BFS() { memset(deep,0,sizeof(deep)); deep[s]=1; queue<int>q; q.push(s); while(q.size()!=0) { int p=q.front(); q.pop(); for(int i=head[p];i!=-1;i=edge[i].nxt) if(!deep[edge[i].v]&&edge[i].flow) { deep[edge[i].v]=deep[edge[i].u]+1;q.push(edge[i].v); if(edge[i].v==t) return 1; } } return deep[t]; } int DFS(int now,int nowflow) { if(now==t||nowflow<=0) return nowflow; int totflow=0; for(int &i=cur[now];i!=-1;i=edge[i].nxt) { if(deep[edge[i].v]==deep[edge[i].u]+1&&edge[i].flow) { int canflow=DFS(edge[i].v,min(nowflow,edge[i].flow)); edge[i].flow-=canflow; edge[i^1].flow+=canflow; totflow+=canflow; nowflow-=canflow; if(nowflow<=0) break; } } return totflow; } int Dinic() { int ans=0; while(BFS()) { for(int i=0;i<=n;i++) cur[i]=head[i]; ans+=DFS(s,1e8); } return ans; } int main() { #ifdef WIN32 freopen("a.in","r",stdin); #else #endif n=read();m=read();s=0;t=n+1; memset(head,-1,sizeof(head)); for(int i=1;i<=m;i++) { int x=read(),y=read(),lower=read(),upper=read();L[i-1]=lower; add_edge(x,y,upper-lower);A[x]-=lower;A[y]+=lower; } int sum=0; for(int i=1;i<=n;i++) { if(A[i]>0) sum+=A[i],add_edge(s,i,A[i]); else add_edge(i,t,-A[i]); } if(Dinic()!=sum) printf("NO"); else { printf("YES\n"); for(int i=0;i<m;i++) printf("%d\n",edge[i*2|1].flow+L[i]); } return 0; }
这篇关于LOJ #115. 无源汇有上下界可行流的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)