zoj2314 Reactor Cooling --- 上下界可行流
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了zoj2314 Reactor Cooling --- 上下界可行流,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2533字,纯文字阅读大概需要4分钟。
内容图文
题目给出了每条边的上下界,
此类题目的建边方法是:
1、添加源点汇点,
2、对每条边 添加边 c(u,v) = up(u,v) - low(u,v)
3、对每个点 c(s,v) = out(v)
c(v,t) = in(v) (权值为正)
求s到t的最大流,若最大流等于所有边下界的和,则存在可行流,
每条边的流量为 flow(u,v) +low(u,v)
#include <iostream> #include <cstring> #include <string> #include <cstdio> #include <cmath> #include <algorithm> #include <vector> #include <queue> #include <map> #define inf 0x3f3f3f3f #define eps 1e-6 #define ll __int64 const int maxn=210; const int maxm=40010; using namespace std; int n,m,s,t,low[maxm],in[maxn],out[maxn]; struct node { int from,to,cap,flow; }; struct dinic { int n,m,s,t; vector<node> e; vector<int> g[maxn]; bool vis[maxn]; int d[maxn]; int cur[maxn]; void init(int n) { e.clear(); for(int i=0;i<=n+1;i++) g[i].clear(); } void addedge(int a,int b,int c,int d)//c d为正向弧和反向弧的权值 一般反向弧为0 { e.push_back((node){a,b,c,0}); e.push_back((node){b,a,d,0}); m=e.size(); g[a].push_back(m-2); g[b].push_back(m-1); } bool bfs() { memset(vis,0,sizeof vis); queue<int> q; q.push(s); d[s]=0; vis[s]=1; while(!q.empty()) { int x=q.front();q.pop(); for(int i=0;i<g[x].size();i++) { node& ee=e[g[x][i]]; if(!vis[ee.to]&&ee.cap>ee.flow) { vis[ee.to]=1; d[ee.to]=d[x]+1; q.push(ee.to); } } } return vis[t]; } int dfs(int x,int a) { if(x==t||a==0) return a; int flow=0,f; for(int& i=cur[x];i<g[x].size();i++) { node& ee=e[g[x][i]]; if(d[x]+1==d[ee.to]&&(f=dfs(ee.to,min(a,ee.cap-ee.flow)))>0) { ee.flow+=f; e[g[x][i]^1].flow-=f; flow+=f; a-=f; if(a==0) break; } } return flow; } int maxflow(int s,int t) { this->s=s; this->t=t; int flow=0; while(bfs()) { memset(cur,0,sizeof cur); flow+=dfs(s,inf); } return flow; } void output(int cnt) { for(int i=0;i<cnt;i++) printf("%d\n",e[i*2].flow+low[i]); } }; dinic solve; int main() { int icy,a,b,cc,d,i,full; scanf("%d",&icy); while(icy--) { scanf("%d%d",&n,&m); s=0,t=n+1; solve.init(n); memset(in,0,sizeof in); memset(out,0,sizeof out); for(i=0;i<m;i++) { scanf("%d%d%d%d",&a,&b,&low[i],&d); solve.addedge(a,b,d-low[i],0); out[a]+=low[i]; in[b]+=low[i]; } full=0; for(i=1;i<=n;i++) { if(out[i]<in[i]) { solve.addedge(s,i,in[i]-out[i],0); full+=in[i]-out[i]; } else solve.addedge(i,t,out[i]-in[i],0); } if(solve.maxflow(s,t)!=full) printf("NO\n"); else { printf("YES\n"); solve.output(m); } } return 0; }
原文:http://blog.csdn.net/u011032846/article/details/38356557
内容总结
以上是互联网集市为您收集整理的zoj2314 Reactor Cooling --- 上下界可行流全部内容,希望文章能够帮你解决zoj2314 Reactor Cooling --- 上下界可行流所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。