上下界網絡流的問題嚴格的分，可以分為四類吧。 1：無源匯可行流 sgu 194 2：有源匯可行流 poj 2396 這題比較好，我建圖建了將近200行 3：有源匯最大流 zoj 3496 這題比較勁爆，需要兩次二分 4：有源匯最小流 hdu 3157 sgu 176 下面三種都是先轉換成無源匯的來做，所以重點講無源匯的網絡流怎麼做。上面兩篇鏈接裡的我就不再贅述了。 假設一條邊的上界流為R 下界流為L，則 R-L為自由流，意思就是只要流了L，接下來要流多少隨便。 無源匯的上下界可行流是指一種方案。流是循環在流的，每個點都滿足流入等於流出。我們再細分一下就是sigma(進來的下界流) + sigma(進來的自由流) = sigma(出去的下界流)+sigma(出去的自由流) 假設我們要將這個網絡流問題轉換成普通的最大流問題，那麼首先就是要把下界去掉，即下界為0。 去掉後要把下界的因素疊加在原圖中，怎麼疊加呢？ 假設一個點進來的下界流總和減去出去的下界流總和為M，如果M為正，表示進來的自由流要比出去的自由流 少 M ，所以我們人為的向這個點補充進M（想想為什麼）。如果M為負，也是類似的，從當前點額外地流出去M。 補充進流量和流出去需要建一個源點，一個匯點。 為什麼這樣子建好圖求最大流後如果源點流出的邊滿流就有解？ 想想看，如果源點流出的邊都能滿流，意味著什麼？？我們可以把中間的網絡看成一個黑箱，源點是入口，匯點是出口，不管中間是循環的流也好，或者是直接經過一條鏈到達匯點也好，我們不關心，我們關心的只是進去的流能否流出來，其實也就是黑箱裡的網絡能否支持流進來的流。如果能夠支持，說明原網絡能夠支持這麼些必須要流的自由流。也就意味著原網絡存在一個方案喽！ 有源匯上下界的最大流的做法是：由匯點T向源點S建邊（上界為INF，下界為0），（這一步非常犀利，等一下解釋為啥麼犀利），轉換成無源匯的網絡流問題，用上面的方法判斷是否有解，如果有解的話，再跑一次源點S到匯點T的最大流，現在的最大流就是答案啦。。。 剛才那一步犀利犀利在只建了一條邊就將原圖轉換成另一個已經可以解決的問題了（也許你不感覺犀利，但從無到有的想出這個方法在本菜看來實在犀利） 第一次跑完最大流的時候其實就可以求解網絡中的一個可行流的流量了，這個流量其實就是最後加進去的那條邊的反向流。因為加進去的時候下界是為0的，因此顯然是正確的。 為什麼最後再跑一遍最大流就能求得答案？ 因為第一遍跑的是可行流，可能還有些邊有余力可以再流一流，所以再跑一遍，原來那個可行流的流量記錄在了T ->S的 反向流中，因次這個流再流一次就流回去了，所以再留一次就是答案！ 好了，既然有下界，那肯定也可以求最小流。 先在原圖中跑一遍最大流，然後連上T-> S (0,INF) 的邊，再跑一遍 關於為什麼第一遍跑的時候那個流量可能不是最小流，開頭第一篇博客中已經有講為什麼了（環） 例題：poj 2396。 題意：有一個矩陣，告訴你每行的和以及每列的和，還有一些限制，綜合起來其實就是告訴你某個數a[i][j]的范圍，不過要自己去求。最後問你是否存在這樣一個矩陣，有的話輸出。 想仔細一點就可以看出這是個很裸的上下界流，但要先拆點，1~n*m表示矩陣中的點，n*m+1~到2*n*m表示拆成的點，2*n*m+1~2*n*m+m表示每一行，2*n*m+m+1~2*n*m+m+n表示每一列，那每行的和 每列的和可以通過新建源點，匯點來限制了，這些邊的上下界都是一個定值，其余的就比較簡單了，套個有源匯的上下界最大流就ok了。 [cpp] #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; const int MAX=10100; const int INF=1000000000; struct EDGE { int v,c,next; }edge[101000]; int E,head[MAX]; int gap[MAX],cur[MAX]; int pre[MAX],dis[MAX]; void add_edge(int s,int t,int c,int cc) { edge[E].v=t; edge[E].c=c; edge[E].next=head[s]; head[s]=E++; edge[E].v=s; edge[E].c=cc; edge[E].next=head[t]; head[t]=E++; } int min(int a,int b){return (a==-1||b<a)?b:a;} int SAP(int s,int t,int n) { memset(gap,0,sizeof(gap)); memset(dis,0,sizeof(dis)); int i; for(i=0;i<n;i++)cur[i]=head[i]; int u=pre[s]=s,maxflow=0,aug=-1,v; gap[0]=n; while(dis[s]<n) { loop: for(i=cur[u];i!=-1;i=edge[i].next) { v=edge[i].v; if(edge[i].c>0&&dis[u]==dis[v]+1) { aug=min(aug,edge[i].c); pre[v]=u; cur[u]=i; u=v; if(u==t) { for(u=pre[u];v!=s;v=u,u=pre[u]) { edge[cur[u]].c-=aug; edge[cur[u]^1].c+=aug; } maxflow+=aug; aug=-1; } goto loop; } } int mindis=n; for(i=head[u];i!=-1;i=edge[i].next) { v=edge[i].v; if(edge[i].c>0&&dis[v]<mindis) { cur[u]=i; mindis=dis[v]; } } if((--gap[dis[u]])==0)break; gap[dis[u]=mindis+1]++; u=pre[u]; } return maxflow; } int m , n , S, T; int sum_row[210] , sum_col[210]; int low[210][210] , up[210][210] ,in[10010]; bool judge(int i,int j,char op,int c) { if(op=='=') { if(c >= low[i][j] && c <= up[i][j]) { low[i][j] = c; up[i][j] = c; } else return false; } else if(op=='>') { low[i][j] = max(low[i][j],c+1); if(low[i][j] > up[i][j]) return false; } else { up[i][j] = min(up[i][j],c-1); if(low[i][j] > up[i][j]) return false; } return true; } bool init() { E=0; memset(head,-1,sizeof(head)); memset(in,0,sizeof(in)); int i , j , k , a, b , c; scanf("%d%d",&m,&n); int tot = 2 * n * m; S = 0; T = tot + n + m + 1; for(i = 1; i <= m; i++) { scanf("%d",&sum_row[i]); in[i+tot] = sum_row[i]; in[S] -= sum_row[i]; //add_edge(S,i+tot,sum_row[i],0); } for(i = 1; i <= n; i++) { scanf("%d",&sum_col[i]); in[T] += sum_col[i]; in[m+tot+i] = - sum_col[i]; //add_edge(m+tot+i,T,sum_col[i],0); } add_edge(T,S,INF,0); scanf("%d",&k); char op[5]; for(i = 1; i <= m; i++) for(j = 1; j <= n; j++) low[i][j] = 0, up[i][j] = 200000; bool flag = true; for(int x = 0; x < k; x++) { scanf("%d%d%s%d",&a,&b,op,&c); if(!a) { if(!b) { for(i = 1; i <= m; i++) { for(j = 1; j <= n; j++) { if(!judge(i,j,op[0],c)) flag = false; } } } else { for(i = 1; i <= m; i++) { if(!judge(i,b,op[0],c)) flag = false; } } } else { if(!b) { for(i = 1; i <= n; i++) { if(!judge(a,i,op[0],c)) flag = false; } } else { if(!judge(a,b,op[0],c)) flag = false; } } } /* for(i = 1; i <= m; i++) { for(j = 1; j <= n; j++) { printf("i = %d j = %d %d %d \n",i , j , low[i][j],up[i][j] ); } } */ return flag; } int ID(int i,int j) { return (i-1)*n+j; } int ans[250][250]; bool check() { for(int i = 1; i <= m; i++) { int s = 0; for(int j =1; j <=n;j ++) { s += ans[i][j]; } if(s!=sum_row[i]) return false; } for(int i = 1; i <= n; i++) { int s = 0; for(int j = 1; j <= m; j++) { s += ans[j][i]; } if(s!=sum_col[i]) return false; } return true; } bool solve() { int i , j , k; for(i = 1; i <= m; i++) { for(j = 1; j <= n; j++) { int c = up[i][j] - low[i][j]; int id = ID(i,j); // printf("i=%d j=%d id = %d %d c = %d\n",i,j,id,id+n*m,c); add_edge(id,id+n*m,c,0); in[id] -= low[i][j]; in[id+n*m] += low[i][j]; } } int ss = T + 1, tt = ss + 1; for(i = 1; i <= m; i++) { for(j = 1; j <= n; j++) { add_edge(2*n*m+i,ID(i,j),200000,0); } } for(i = 1; i <= n; i++) { for(j = 1; j <= m; j++) { //printf("%d %d\n",2*n*m+m+i,ID(j,i)+n*m); add_edge(ID(j,i)+m*n,2*m*n+m+i,200000,0); } } for(i = 0; i <= 2*m*n+m+n+1 ; i++) { //printf("in[%d]=%d\n",i,in[i]); if(in[i] > 0) add_edge(ss,i,in[i],0); if(in[i] < 0) add_edge(i,tt,-in[i],0); } SAP(ss,tt,tt+1); for(i=head[ss];i!=-1;i=edge[i].next) { if(edge[i].c) return false; } for(i = 1; i <= m; i++) { for(j = 1; j <= n; j++) { int id = ID(i,j); for(k = head[id]; k!=-1; k=edge[k].next) { if(edge[k].v <= 2*n*m) { ans[i][j] = low[i][j] + edge[k^1].c; } } } } for(i = 1; i <= m; i++) { printf("%d",ans[i][1]); for(j = 2; j <= n; j++) { printf(" %d",ans[i][j]); } puts(""); } /* if(check()) { puts("YES"); } else puts("NO");*/ return true; } int main() { int t; // freopen("budget.in","r",stdin); // freopen("budget.out","w",stdout); scanf("%d",&t); for(int i = 0; i < t; i++) { if(i) puts(""); if(!init()) { puts("IMPOSSIBLE"); } else { if(!solve()) puts("IMPOSSIBLE"); } } return 0; } zoj 那題很好想，需要兩次二分，但不是太好寫，附上代碼吧。 [cpp] http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3496 #include<stdio.h> #include<string.h> typedef long long lld; const int MAX=510; const int INF=100000000; struct EDGE { int v,c,next; }edge[1000000]; int E,head[MAX]; int gap[MAX],cur[MAX]; int pre[MAX],dis[MAX]; void add_edge(int s,int t,int c,int cc) { edge[E].v=t; edge[E].c=c; edge[E].next=head[s]; head[s]=E++; edge[E].v=s; edge[E].c=cc; edge[E].next=head[t]; head[t]=E++; } int min(int a,int b){return (a==-1||b<a)?b:a;} int SAP(int s,int t,int n) { memset(gap,0,sizeof(gap)); memset(dis,0,sizeof(dis)); int i; for(i=0;i<n;i++)cur[i]=head[i]; int u=pre[s]=s,aug=-1,v; int maxflow = 0; gap[0]=n; while(dis[s]<n) { loop: for(i=cur[u];i!=-1;i=edge[i].next) { v=edge[i].v; if(edge[i].c>0&&dis[u]==dis[v]+1) { aug=min(aug,edge[i].c); pre[v]=u; cur[u]=i; u=v; if(u==t) { for(u=pre[u];v!=s;v=u,u=pre[u]) { edge[cur[u]].c-=aug; edge[cur[u]^1].c+=aug; } maxflow+=aug; aug=-1; } goto loop; } } int mindis=n; for(i=head[u];i!=-1;i=edge[i].next) { v=edge[i].v; if(edge[i].c>0&&dis[v]<mindis) { cur[u]=i; mindis=dis[v]; } } if((--gap[dis[u]])==0)break; gap[dis[u]=mindis+1]++; u=pre[u]; } return maxflow; } int n , m , S , T , P , ans1 , ans2 , maxc , minc; int max_flow; int u[10010] , v[10010] , c[10010]; int in[510]; void init() { E = 0; memset(head,-1,sizeof(head[0])*600); } void Map_Init(int mid) // 流量上界為mid ，每條邊的上界就是mid與c的最小值 { init(); for(int i = 0; i < m; i++) { add_edge(u[i],v[i],min(mid,c[i]),0); } } void question1() // 二分上界 { int l = 0 , r = maxc; while(l <= r) { int mid = l + r >> 1; Map_Init(mid); int tmp = SAP(S,T,n); if(tmp == max_flow) { ans1 = mid; r = mid - 1; } else { l = mid + 1; } } } bool map_init(int mid)//mid 為下界 { init(); memset(in,0,sizeof(in)); for(int i = 0; i < m; i++) { if(c[i] < mid) return false; add_edge(u[i],v[i],c[i]-mid,0); in[v[i]] += mid; in[u[i]] -= mid; } return true; } bool ok(int mid) { int i , j; if(!map_init(mid)) return false; int ss = n , tt = n + 1; for(i = 0; i < n ; i++) { www.2cto.com if(in[i] > 0) add_edge(ss,i,in[i],0); if(in[i] < 0) add_edge(i,tt,-in[i],0); } add_edge(T,S,INF,0); SAP(ss,tt,tt+1); for(i = head[ss];i!=-1;i=edge[i].next) { if(edge[i].c) return false; } return SAP(S,T,tt+1) == max_flow; } void question2() // 二分下界 { int l = 0 , r = maxc ;// 理論上講這個r賦為minc是可以的，但是WA了（因為如果大於minc就一定會有邊的上界小於下界） while(l <= r) { int mid = l + r >> 1; if(ok(mid)) { ans2 = mid; l = mid + 1; } else { r = mid - 1; } } } int main() { int t,i,j,k; scanf("%d",&t); while(t--) { scanf("%d%d%d%d%d",&n,&m,&S,&T,&P); init(); maxc = 0; minc = INF; for(i=0;i<m;i++) { scanf("%d%d%d",&u[i],&v[i],&c[i]); add_edge(u[i],v[i],c[i],0); if(c[i] > maxc) maxc = c[i]; if(c[i] < minc) minc = c[i]; } max_flow = SAP(S,T,n); question1(); question2(); printf("%lld %lld\n",(lld)ans1*P,(lld)ans2*P); } return 0; } /* 100 4 3 0 3 3 0 1 2 1 2 3 2 3 4 4 5 0 3 2 0 1 2 0 2 1 1 2 1 1 3 1 2 3 2 4 5 0 3 2 0 1 1 0 2 1 1 2 2 1 3 2 2 3 1 5 5 0 4 1 0 3 1 0 2 1 3 1 1 2 1 1 1 4 1 6 6 4 2 2 0 1 0 */ 最後再總結一下建圖方法，方便現場賽可以快速的回憶起來。 1：無源匯的可行流 ： 新建源點，匯點，M[i]為每個點進來的下界流減去出去的下界流，如果M[i]為正，由源點向改點建M[i]的邊，反之，由該點向匯點建M[i]的邊，原圖中的邊為每條邊的上界建去下界。跑一遍最大流，每條邊的流量加上下界流就是答案。 2：有源匯的最大流： 從匯點向源點建一條容量為INF的邊，用上面的方法判斷是否有解，有解就再跑一遍從原圖中源點到匯點的最大流 3：有源匯的最小流：先跑一遍最大流，然後連上從匯點到源點的邊，再按照1的方法做就好了
