首页 > 代码库 > ZOJ 2314 Reactor Cooling 带上下界的网络流
ZOJ 2314 Reactor Cooling 带上下界的网络流
题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1314
题意：
给n个点，及m根pipe，每根pipe用来流躺液体的，单向的，每时每刻每根pipe流进来的物质要等于流出去的物质，要使得m条pipe组成一个循环体，里面流躺物质。
并且满足每根pipe一定的流量限制，范围为[Li,Ri].即要满足每时刻流进来的不能超过Ri(最大流问题)，同时最小不能低于Li。
求的是最大流。
很久之前就看了带上下界的网络流，一直没看懂，以为刘汝佳的书上写错了，哈哈~~~
建图：
修改成普通的网络流，但是要保证流量守恒，那么，ss到v的容量，u到tt的容量为 b，而且，要这些附加的边上的流必须满载。
然后题目要求最大的流，那么要把这个可行流找出来，这样，我建边的时候，先不加ss,tt的边，
这样，可行流就在edge[i*2]的地方。
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 #define inf 0x3f3f3f3f 6 7 const int maxn = 40010; 8 9 //int low[maxn],in[maxn],out[maxn]; 10 11 struct Edge 12 { 13 int from,to,cap,flow; 14 }; 15 16 struct Dinic 17 { 18 int n,m,s,t; 19 vector<Edge> edge; 20 vector<int> G[maxn]; 21 bool vis[maxn]; 22 int d[maxn]; 23 int cur[maxn]; 24 25 void init() 26 { 27 for(int i=0;i<maxn;i++) 28 G[i].clear(); 29 edge.clear(); 30 memset(d,0,sizeof(d)); 31 memset(vis,0,sizeof(vis)); 32 memset(cur,0,sizeof(cur)); 33 } 34 35 void AddEdge (int from,int to,int cap) 36 { 37 edge.push_back((Edge){from,to,cap,0}); 38 edge.push_back((Edge){to,from,0,0}); 39 m = edge.size(); 40 G[from].push_back(m-2); 41 G[to].push_back(m-1); 42 } 43 44 bool BFS() 45 { 46 memset(vis,0,sizeof(vis)); 47 queue<int> Q; 48 Q.push(s); 49 d[s] = 0; 50 vis[s] = 1; 51 while(!Q.empty()) 52 { 53 int x = Q.front(); 54 Q.pop(); 55 for(int i=0; i<G[x].size(); i++) 56 { 57 Edge & e = edge[G[x][i]]; 58 if(!vis[e.to]&&e.cap>e.flow) 59 { 60 vis[e.to] = 1; 61 d[e.to] = d[x] + 1; 62 Q.push(e.to); 63 } 64 } 65 } 66 return vis[t]; 67 } 68 69 long long DFS(int x,int a) 70 { 71 if(x==t||a==0) return a; 72 long long flow = 0,f; 73 for(int & i = cur[x]; i<G[x].size(); i++) 74 { 75 Edge & e = edge[G[x][i]]; 76 if(d[x] + 1==d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0) 77 { 78 e.flow +=f; 79 edge[G[x][i]^1].flow -=f; 80 flow +=f; 81 a-=f; 82 if(a==0) break; 83 } 84 } 85 return flow; 86 } 87 88 int Maxflow (int s,int t) { 89 this->s = s;this->t = t; 90 int flow = 0; 91 while(BFS()) { 92 memset(cur,0,sizeof(cur)); 93 flow+=DFS(s,inf); 94 } 95 return flow; 96 } 97 98 void print(int cnt) { 99 for(int i=0;i<cnt;i++)100 printf("%d\n",edge[i*2].flow+edge[G[0][i]].flow);101 }102 103 }sol;104 105 106 int main()107 {108 int t;109 scanf("%d",&t);110 while(t--) {111 int n,m;112 scanf("%d%d",&n,&m);113 int low[maxn],uu[maxn],vv[maxn];114 int sum = 0;115 sol.init();116 for(int i=0;i<m;i++) {117 int u,v,b,c;118 scanf("%d%d%d%d",&u,&v,&b,&c);119 low[i] = b;120 uu[i] = u;121 vv[i] = v;122 sol.AddEdge(u,v,c-b);123 sum+=b;124 // out[u] +=low[i];125 // in[v] +=low[i];126 // sol.AddEdge(0,v,b);127 // sol.AddEdge(u,n+1,b);128 }129 130 for(int i=0;i<m;i++) {131 sol.AddEdge(0,vv[i],low[i]);132 sol.AddEdge(uu[i],n+1,low[i]);133 }134 135 int maxflow = sol.Maxflow(0,n+1);136 if(sum!=maxflow)137 puts("NO");138 else {139 puts("YES");140 // for(int i=0;i<sol.G[0].size();i++) {141 // printf("%d\n",sol.edge[sol.G[0][i]].flow);142 // }143 sol.print(m);144 }145 }146 return 0;147 }
ZOJ 2314 Reactor Cooling 带上下界的网络流
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。