上下流相關的網絡流的各種問題在Amber大牛的《圖論原理》裡講的特備清楚。。。。。資料需要網上下載下傳。。我就把原文摘抄下來吧。。。。。。
問題模型：
給定一個權重的有向圖，滿足：
(1)容量限制條件：
(2)流量平衡條件：
(2)中的
即除了源彙外，所有點都滿足流量平衡條件，則稱G為有源彙網絡；否則
，即不存在源彙，所有點都滿足流量平衡條件，則稱G為無源彙網絡。
将這類問題由易到難一一解決：
問題[1] 求無源彙的網絡有上下界的可行流
由于下界是一條弧上的流必需要滿足的确定值。下面引入必要弧的概念：必要弧是一定流要滿的弧。必要弧的構造，将容量下界的限制分離開了，進而構造了一個沒有下界的網絡G’：
1． 将原弧(u,v)分離出一條必要弧：
。（紅色表示）
2． 原弧：
。
由于必要弧的有一定要滿的限制，将必要弧“拉”出來集中考慮：
添加附加源x, 附加彙y。想像一條不限上界的(y, x)，用必要弧将它們“串”起來，即對于有向必要弧(u, v)，添加(u, y)，(x, v)，容量為必要弧容量。這樣就建立了一個等價的網絡。
一個無源彙網絡的可行流的方案一定是必要弧是滿的。若去掉(y, x)後，附加源x到附加彙y的最大流，能使得x的出弧或者y的入弧都滿，充要于原圖有可行流。
算法：
1. 按上述方法構造新網絡(分離必要弧，附加源彙)
2. 求附加源x到附加彙y的最大流
3. 若x的出弧或y的入弧都滿，則有解，将必要弧合并回原圖；否則，無解。
問題[2] 求有源彙的網絡有上下界的可行流
加入邊(t, s)，下界為0(保證不會連上附加源彙x, y)，不限上界，将問題[2]轉化為問題[1]來求解。
問題[3]求有源彙的網絡有上下界的最大流
算法：
1. 先轉化為問題[2]來求解一個可行流。若可行無解，則退出。由于必要弧是分離出來的，是以就可以把必要弧（附加源彙及其臨邊）及其上的流，暫時删去。再将(T,S)删去，恢複源彙。
2. 再次，從S到T找增廣軌，求最大流。
3. 最後将暫時删去的下界資訊恢複，合并到目前圖中。輸出解。
這樣既不破壞下界(分離出來)也不超出上界(第2步滿足容量限制)，問題解決。
問題[4]求有源彙的網絡有上下界的最小流
算法：
1. 同問題[3]。
2. 從T到S找增廣軌，不斷反着改進。
3. 同問題[3]。
問題[3]與問題[4]的另一種簡易求法：
注意問題[2]中，構造出的(t, s)，上下界幾乎沒什麼限制。下面看看它的性質：
定理：如果從s到t有一個流量為a的可行流f，那麼從t到s連一條弧(t, s)，其流量下界b(t, s) = a，則這個圖一定有一個無源彙的可行流：除了弧(t, s)的容量為a外，其餘邊的容量與f相同。
證明：如果從s到t的最大流量為amax，那麼從t到s連一條下界b(t, s) = a’ > amax的弧(t, s)，則從在這個改造後的圖中一定沒有無源彙的可行流：否則将這個可行流中的弧(t, s)除去，就得到了原圖中s到t的流量為a’的流，大于最大流量amax，産生沖突。
可以二分枚舉這個參數a，即下界b(t, s)，每次用問題[1]判斷是否有可行流。這樣就可以求出最大流。
同理，問題[4]要求最小流，隻要二分枚舉上界c(t, s)即可。
因為樸素的預流推進算法O(N3)，總複雜度為O(N3 log2流量) 。
思路：
無源彙 (附加源彙+最大解決)
有源彙 (附加(T,S)->無源彙)
根據這個講解自己寫一個相應的程式就可以了。。。這個題裡面。。把每一行看成一個點。。每一列看成一個點來建圖。。。。（IMPOSSIBLE少寫一個s wa了半天。。揮淚呀。。。。TT。。。）
還有就是網上的上下界的網絡流之類的的題不是很多。。。建議好好刷每一道題。。。。。
( 在給一個小小的OJ bug就是雖然說每兩個case間輸出空行。。其實不要理會。。。每個case都輸出也會是對的。。。。OJ不會去判最後的那一行有沒有空行。。。。不過隻試用于現階段呀。。。有一次校賽。。就專門卡這個。。還提示wa。。。可想而知當時的結果。。。。。)
Budget
| Time Limit: 3000MS | Memory Limit: 65536K | |
| Total Submissions: 3469 | Accepted: 1313 | Special Judge |
Description
We are supposed to make a budget proposal for this multi-site competition. The budget proposal is a matrix where the rows represent different kinds of expenses and the columns represent different sites. We had a meeting about this, some time ago where we discussed the sums over different kinds of expenses and sums over different sites. There was also some talk about special constraints: someone mentioned that Computer Center would need at least 2000K Rials for food and someone from Sharif Authorities argued they wouldn't use more than 30000K Rials for T-shirts. Anyway, we are sure there was more; we will go and try to find some notes from that meeting.
And, by the way, no one really reads budget proposals anyway, so we'll just have to make sure that it sums up properly and meets all constraints.
Input
The first line of the input contains an integer N, giving the number of test cases. The next line is empty, then, test cases follow: The first line of each test case contains two integers, m and n, giving the number of rows and columns (m <= 200, n <= 20). The second line contains m integers, giving the row sums of the matrix. The third line contains n integers, giving the column sums of the matrix. The fourth line contains an integer c (c < 1000) giving the number of constraints. The next c lines contain the constraints. There is an empty line after each test case.
Each constraint consists of two integers r and q, specifying some entry (or entries) in the matrix (the upper left corner is 1 1 and 0 is interpreted as "ALL", i.e. 4 0 means all entries on the fourth row and 0 0 means the entire matrix), one element from the set {<, =, >} and one integer v, with the obvious interpretation. For instance, the constraint 1 2 > 5 means that the cell in the 1st row and 2nd column must have an entry strictly greater than 5, and the constraint 4 0 = 3 means that all elements in the fourth row should be equal to 3.
Output
For each case output a matrix of non-negative integers meeting the above constraints or the string "IMPOSSIBLE" if no legal solution exists. Put one empty line between matrices.
Sample Input
2
2 3
8 10
5 6 7
4
0 2 > 2
2 1 = 3
2 3 > 2
2 3 < 5
2 2
4 5
6 7
1
1 1 > 10
Sample Output
2 3 3
3 3 4
IMPOSSIBLE #include<iostream>
#include<cstdio>
#include<string>
using namespace std;
#define maxM 50000
#define maxN 500
#define inf 1<<30
struct node{
int u,v,f,next;
}edge[maxM];
int head[maxN],p,lev[maxN],cur[maxN];
int que[maxM],tre[maxN],up[maxN][50],low[maxN][50];
void init1(int n,int m){
p=0,memset(head,-1,sizeof(head)),memset(tre,0,sizeof(tre));
for(int i=0;i<=n;i++) for(int j=0;j<=m;j++)
up[i][j]=inf,low[i][j]=0;
}
bool bfs(int s,int t){
int qin=0,qout=0,u,i,v;
memset(lev,0,sizeof(lev));
lev[s]=1,que[qin++]=s;
while(qout!=qin){
u=que[qout++];
for(i=head[u];i!=-1;i=edge[i].next){
if(edge[i].f>0 && lev[v=edge[i].v]==0){
lev[v]=lev[u]+1,que[qin++]=v;
if(v==t) return 1;
}
}
}
return lev[t];
}
int dinic(int s,int t){
int qin,u,i,k,f;
int flow=0;
while(bfs(s,t)){
memcpy(cur,head,sizeof(head));
u=s,qin=0;
while(1){
if(u==t){
for(k=0,f=inf;k<qin;k++)
if(edge[que[k]].f<f)
f=edge[que[i=k]].f;
for(k=0;k<qin;k++)
edge[que[k]].f-=f,edge[que[k]^1].f+=f;
flow+=f,u=edge[que[qin=i]].u;
}
for(i=cur[u];cur[u]!=-1;i=cur[u]=edge[cur[u]].next)
if(edge[i].f>0 && lev[u]+1==lev[edge[i].v]) break;
if(cur[u]!=-1)
que[qin++]=cur[u],u=edge[cur[u]].v;
else{
if(qin==0) break;
lev[u]=-1,u=edge[que[--qin]].u;
}
}
}
return flow;
}
void addedge(int u,int v,int f){
edge[p].u=u,edge[p].v=v,edge[p].f=f,edge[p].next=head[u],head[u]=p++;
edge[p].u=v,edge[p].v=u,edge[p].f=0,edge[p].next=head[v],head[v]=p++;
}
bool buit(int n,int m){
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(low[i][j]>up[i][j]) return 0;
else{
tre[i]-=low[i][j],tre[j+n]+=low[i][j];
addedge(i,j+n,up[i][j]-low[i][j]);
}
return 1;
}
void limitflow(int s,int t,int n,int m){
int i,j,x,y;
x=t+1,y=t+2;
for(i=0;i<=t;i++){
if(tre[i]>0) addedge(x,i,tre[i]);
else if(tre[i]<0) addedge(i,y,-tre[i]);
}
addedge(t,s,inf);
dinic(x,y);
for(i=head[x];i!=-1;i=edge[i].next)
if(edge[i].f){
printf("IMPOSSIBLE\n\n"); return ;
}
for(i=head[t];i!=-1;i=edge[i].next)
if(edge[i].v==s) break;
if(i<0){
printf("IMPOSSIBLE\n\n"); return;
}
for(i=1;i<=n;i++){
for(j=1;j<m;j++)
printf("%d ",edge[((i-1)*m+j)*2-1].f+low[i][j]);
printf("%d\n",edge[i*m*2-1].f+low[i][j]);
}
printf("\n");
}
int main(){
int cas,cas1,n,m,i,j,sum1,sum2;
int u,v,d,f1,t1,f2,t2,s,t;
char c[5];
scanf("%d",&cas);
for(int tt=1;tt<=cas;tt++){
scanf("%d%d",&n,&m);
s=0,t=n+m+1,sum1=0,sum2=0;
init1(n,m);
for(i=1;i<=n;i++) scanf("%d",&u),tre[s]-=u,tre[i]+=u,sum1+=u;;
for(i=n+1;i<=n+m;i++) scanf("%d",&u),tre[i]-=u,tre[t]+=u,sum2+=u;
scanf("%d",&cas1);
while(cas1--){
scanf("%d%d%s%d",&u,&v,c,&d);
f1=t1=u,f2=t2=v;
if(u==0) f1=1,t1=n;
if(v==0) f2=1,t2=m;
for(i=f1;i<=t1;i++)
for(j=f2;j<=t2;j++){
if(c[0]=='='){
low[i][j]=max(d,low[i][j]),up[i][j]=min(d,up[i][j]);
}else if(c[0]=='>'){
low[i][j]=max(d+1,low[i][j]);
}else if(c[0]=='<'){
up[i][j]=min(d-1,up[i][j]);
}
}
}
if(sum1==sum2 && buit(n,m)) limitflow(s,t,n,m);
else printf("IMPOSSIBLE\n\n");
}
return 0;
}