有上下界網(wǎng)絡(luò)流問地的題目

1、有上下界網(wǎng)絡(luò)流問題1. 無源匯最大流2. 有源匯最大流3. 有源匯最小流1.無源匯最大流問題sgu194題意：給n個(gè)點(diǎn)，及m根pipe，每根pipe用來流躺液體的，單向的，每時(shí)每刻每根pipe流進(jìn)來的物質(zhì)要等于流出去的物質(zhì)，要使得m條pipe組成一個(gè)循環(huán)體，里面流躺物質(zhì)。并且滿足每根pipe 一定的流量限制，范圍為L(zhǎng)i,Ri.即要滿足每時(shí)刻流進(jìn)來的不能超 過Ri（最大流問題），同時(shí)最小不能低于Li。例如：46（4 個(gè)點(diǎn)，6 個(gè) pipe）12 1 3 （1->2 上界為3，下界為1）23 1 33 4 1 34 1 1 31 3 1 34 2 1 3可行流：再如：所有pipe的上界為2下

2、界為1的話，就不能得到一種可行流。題解：上界用ci表示，下界用bi表示。下界是必須流滿的，那么對(duì)于每一條邊，去掉下界后，其自由流為ci - bi。主要思想：每一個(gè)點(diǎn)流進(jìn)來的流 二流出去的流對(duì)于每一個(gè)點(diǎn)i,令Mi= sum（i點(diǎn)所有流進(jìn)來的下界流）-sum（i點(diǎn)所有流出去的下界流）如果Mi大于0，代表此點(diǎn)必須還要流出去 Mi的自由流，那么我們從源點(diǎn)連一條 Mi的邊到該點(diǎn)。如果Mi小于0，代表此點(diǎn)必須還要流進(jìn)來 Mi的自由流，那么我們從該點(diǎn)連一條 Mi的邊到匯點(diǎn)。如果求S->T的最大流，看是否滿流（S的相鄰邊都流滿）。滿流則有解，否則無解。zoj3229題意：經(jīng)過構(gòu)圖之后得到這樣的問題，源點(diǎn)

3、s,匯點(diǎn)t,有些邊有上下界Li,Ri.求s->t 的最大流。題解: 滿足所有下界的情況下，判斷是否存在可行流，方法可以轉(zhuǎn)化成上面無源匯上下界判斷方法。只要連一條T- S的邊，流量為無窮，沒有下界，那么原圖就得到一個(gè)無源匯的循 環(huán)流圖。接下來的事情一樣：原圖中的邊的流量設(shè)成自由流量ci - bi。新建源點(diǎn)SS匯點(diǎn)TT,求Mi，連邊。然后求SS- TT最大流，判是否滿流。判定有解之后然后求最大流，信息都在上面求得的殘留網(wǎng)絡(luò)里面。滿足所有下界時(shí)，從s- t的流量為多少？后悔邊s- t的邊權(quán)！然后在殘留網(wǎng)絡(luò)中s- t可能還有些 自由流沒有流滿，再做一次s- t的最大流，所得到的最大流就是原問題的

4、最大流（內(nèi) 含兩部分：殘留的自由流所得到的流 +后悔邊s- t）。3.有源匯最小流 題意：經(jīng)過構(gòu)圖之后得到這樣的問題，源點(diǎn)s,匯點(diǎn)t,有些邊有上下界Li,Ri.求s->t 的最小流。題解：同樣先轉(zhuǎn)換為無源匯網(wǎng)絡(luò)流問題，添加t- s邊權(quán)為無窮。那么最小流不就是在滿足所有下界的情況的流么。即上面提到的，求得SS- TT的最大流之后，其后悔邊s t的邊權(quán)即為最小流。但是 wa 了，下面看一個(gè) wa的例子：最后求得SS TT的最大流之后，得到后悔邊 s t的邊權(quán)為200，實(shí)際上該網(wǎng)絡(luò) 最小流只要100 :s 1:1001 3:2003 2:2002 1:1002 t:100問題出在原圖中存在環(huán)，

5、循環(huán)流，而我們沒有利用，導(dǎo)致流增大了。解決方法：先不加tf s邊權(quán)為無窮的邊，求 SS- TT的最大流，如果還沒有流滿 則再加tf s邊權(quán)為無窮的邊，再求一次最大流得到后悔邊 s- t就是原問題的最 小流了。zoj_3229_AC_code:/*求有源匯的最大流問題*/memset(i n,0,sizeof (in); /*初始化出度，入度，用于求Mi*/memset(out,0,sizeof (out);M= n+m+2; /* 初始化網(wǎng)絡(luò)，設(shè)置源點(diǎn)匯點(diǎn)*/s= 0;t= M-1;cnt= -1;memset(mat,0,sizeof (mat);for(int i=1;i<=n;i+

6、) /*添加自由流 */for(int j=1;j<=Ci;j+) addEdge(i, n+Tij,Rij-Lij,0);inn+Tij+= Lij;outi+= Lij;for(i nt i=1;i< 二n ;i+) addEdge(s,i,Di,O);for(i nt i=1;i<=m;i+) addEdge (n+i,t,INF - Gi,O);in t+= Gi;out n+i+二 Gi;addEdge(t,s,INF,0); /* 添加一條 t s 的邊，權(quán)值為 INF*/M+= 2; s = M-1; t = s-1; /* 添加 SS, TT*/ sum二0;

7、/*滿流變量*/for(int i=0;i<M;i+) /* 根據(jù) Mi 連邊*/ if(ini > outi) addEdge(s,i,i ni - outi,0);sum+= in i - outi;else addEdge(i,t,outi - i n i,0);intmaxflow = dinic (); /*求 SS Tt 的最大流 */if(sum != maxflow) /*不滿流則輸出-1*/prin tf("-1nn");con ti nue;mats= 0; /* 刪除 SS, TT*/matt= 0;M= n+m+2;s= 0;t= M-1

8、;maxflow= dinic (); /* 求s t的最大流，為原問題的解 */prin tf("%dn",maxflow);in tmm = -1;for(i nt i=1;i< 二n ;i+) for(int j=1;j<=Ci;j+) mm+;prin tf("%dn",Rij - edge2*mm.cap);prin tf("n");sgu_176_AC_code:/*有源匯的最小流*/Mi*/memset(i n,0,sizeof (in); /*初始化出度，入度，用于求memset(out,0,sizeof

9、(out);M= n+1; /*初始化網(wǎng)絡(luò)，設(shè)置源點(diǎn)匯點(diǎn)*/s= 1;t= M-1;cnt= -1;memset(mat,0,sizeof (mat);for(int i=1;i<=m;i+) /* 添加自由流 */if(ci = 1) in vi += zi;outui += zi;addEdge (ui,vi,0,0);else addEdge (ui,vi,zi,0);M+= 2; s = M-1; t = s-1; /* 添加 SS, TT*/intsum = 0; /*滿流變量 */for(int i=1;i<=n;i+) /* 根據(jù) Mi 連邊*/ if(ini >

10、; outi) addEdge(s,i,i ni - outi,0);sum+= in i - outi;else addEdge(i,t,outi - i n i,0);intmaxflow = dinic (); /*求SS TT的最大流，先流完途中的循環(huán)流 */intmmm = cnt; /* 記錄新加的t f s無窮邊的編號(hào)，以便求后悔邊的權(quán)值*/addEdge(n,1,INF,0); /*添加一條 tf s 的邊，權(quán)值為 INF*/maxflow+= dinic (); /*求 SSf TT 的最大流 */if(sum != maxflow) /* 不滿流則輸出-1*/prin tf("lmpossiblen");return。;printf("%dn",edgemmm+2.cap); /* in tmm = -1;boolfirst = 1;最小流為后悔邊：sf t的權(quán)值*/for(i nt i=1;