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 ",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 ",sol.edge[sol.G[0][i]].flow); 142 // } 143 sol.print(m); 144 } 145 } 146 return 0; 147 }