sgu 194 Reactor Cooling
题意：给n个点，m根pipe，每根pipe有单向的液体流动，每时每刻每根pipe流进来的物质要等于流出去的物质，要使得m条pipe组成一个循环体，并且满足每根pipe一定的流量限制，范围为[Li,Ri].即要满足每时刻流进来的不能超过Ri(最大流问题)，同时最小不能低于Li。 问给定的数据能否构成一个循环体，如果可以，输出每条pipe中流了多少液体。
思路：
无源汇有上下界网络流求可行解
1. 将原网络中的边流量改为 up - low
2. 为了维持每个结点流量平衡，构造一个超级源点，一个超级汇点
3. 统计每个点流入的low值以及流出的low值和，流入为正，流出为负
4. 如果tot[i]为正，则源点向其连边，流量为tot[i]。如果为负，该点向汇点连边，流量为 - tot[i]
5. 做一次最大流，如果从源点流出的每一条边都满流，则存在可行流
这道题目如果存在可行流，还要输出每条pipe中的流量。
每条pipe的流量 = low值 + 新网络求过最大流只会的流量
代码：
/* ID: wuqi9395@126.com PROG: LANG: C++ */ #include<map> #include<set> #include<queue> #include<stack> #include<cmath> #include<cstdio> #include<vector> #include<string> #include<fstream> #include<cstring> #include<ctype.h> #include<iostream> #include<algorithm> using namespace std; #define INF (1 << 30) #define LINF (1LL << 60) #define PI acos(-1.0) #define mem(a,b) memset(a,b,sizeof(a)) #define rep(i,a,n) for (int i = a; i < n; i++) #define per(i,n) for (int i = n - 1; i >= a; i--) #define eps 1e-6 #define debug puts("===============") #define pb push_back #define mkp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) #define POSIN(x,y) (0 <= (x) && (x) < n && 0 <= (y) && (y) < m) typedef long long ll; typedef unsigned long long ULL; const int maxn = 1000; const int maxm = 100000; struct node { int v; // vertex int cap; // capacity int flow; // current flow in this arc int nxt; } e[maxm * 2]; int g[maxn],cnt; int st,ed,n,m; int id[maxm],low[maxm],tot[maxn]; void add(int u,int v,int c,int k) { e[++cnt].v = v; e[cnt].cap = c; e[cnt].flow = 0; e[cnt].nxt = g[u]; g[u] = cnt; id[cnt] = k; e[++cnt].v = u; e[cnt].cap = 0; e[cnt].flow = 0; e[cnt].nxt = g[v]; g[v] = cnt; id[cnt] = 0; } int should; //所构造的新网络中满流为should void init() { memset(g,sizeof(g)); //memset(tot,sizeof(tot)); cnt = 1; int u,v,L,U; st = 0,ed = n + 1; for (int i = 1; i <= m; i++) { scanf("%d%d%d%d",&u,&v,&L,&U); add(u,U - L,i); low[i] = L; tot[u] -= L; tot[v] += L; } should = 0; for (int i = 1; i <= n; i++) { if (tot[i] > 0) add(st,i,tot[i],0),should += tot[i]; if (tot[i] < 0) add(i,-tot[i],0); } n = n + 3; } int dist[maxn],numbs[maxn],q[maxn]; void rev_bfs() { int font = 0,rear = 1; for (int i = 0; i <= n; i++) { //n为总点数 dist[i] = maxn; numbs[i] = 0; } q[font] = ed; dist[ed] = 0; numbs[0] = 1; while(font != rear) { int u = q[font++]; for (int i = g[u]; i; i = e[i].nxt) { if (e[i ^ 1].cap == 0 || dist[e[i].v] < maxn) continue; dist[e[i].v] = dist[u] + 1; ++numbs[dist[e[i].v]]; q[rear++] = e[i].v; } } } int maxflow() { rev_bfs(); int u,totalflow = 0; int curg[maxn],revpath[maxn]; for(int i = 0; i <= n; ++i) curg[i] = g[i]; u = st; while(dist[st] < n) { if(u == ed) { // find an augmenting path int augflow = INF; for(int i = st; i != ed; i = e[curg[i]].v) augflow = min(augflow,e[curg[i]].cap); for(int i = st; i != ed; i = e[curg[i]].v) { e[curg[i]].cap -= augflow; e[curg[i] ^ 1].cap += augflow; e[curg[i]].flow += augflow; e[curg[i] ^ 1].flow -= augflow; } totalflow += augflow; u = st; } int i; for(i = curg[u]; i; i = e[i].nxt) if(e[i].cap > 0 && dist[u] == dist[e[i].v] + 1) break; if(i) { // find an admissible arc,then Advance curg[u] = i; revpath[e[i].v] = i ^ 1; u = e[i].v; } else { // no admissible arc,then relabel this vertex if(0 == (--numbs[dist[u]])) break; // GAP cut,Important! curg[u] = g[u]; int mindist = n; for(int j = g[u]; j; j = e[j].nxt) if(e[j].cap > 0) mindist = min(mindist,dist[e[j].v]); dist[u] = mindist + 1; ++numbs[dist[u]]; if(u != st) u = e[revpath[u]].v; // Backtrack } } return totalflow; } bool lowbound_flow() { if (maxflow() != should) return false; return true; } int ans[maxm]; int main () { scanf("%d%d",&n,&m); init(); if (!lowbound_flow()) puts("NO"); else { puts("YES"); for (int i = 2; i <= cnt; i++) ans[id[i]] = e[i].flow; for (int i = 1; i <= m; i++) printf("%d\n",ans[i] + low[i]); } return 0; }
