網絡流 練習題：流量有下限的最大流

Title: 運輸問題2
Input: maxflowb.in
Output: maxflowb.out
Time Limit: 1000 ms
Memory Limit: 128 MB
Level: ★★★
運輸問題
【問題描述】
一個工廠每天生產若干商品，需運輸到銷售部門進行銷售。從產地到銷地要經過某些城鎮，有不同的路線可以行走，每條兩城鎮間的公路都有一定的流量限制。爲了 保證公路的運營效率，每條公路都有一個容量下界，也就是至少應有多少車輛通過。每條公路還有一個容量上界，也就是最多應有多少車輛通過。請你計算，在不考 慮其它車輛使用公路的前提下，如何充分利用所有的公路，使產地運輸到銷地的商品最多，最多能運輸多少商品。



【輸入格式】
輸入文件有若干行
第一行，一個整數n，表示共有n個城市(2<=n<=100)
下面有n行,每行有2*n個數字。第p行第2*q-1,2*q列的數字表示城鎮p與城鎮q之間有無公路連接。數字爲0表示無，大於0表示有公路，且這兩個數字分別表示該公路流量的下界，上界。
【輸出格式】
輸出文件有一行
第一行，1個整數n，表示最大流量爲n。
【輸入輸出樣例】
輸入文件名： maxflowb.in
6
0 0 1 3 0 10 0 0 0 0 0 0
0 0 0 0 0 0 5 7 0 0 0 0
0 0 0 0 0 0 0 0 2 8 0 0
0 0 0 0 1 3 0 0 0 0 3 5
0 0 2 4 0 0 0 0 0 0 2 6
0 0 0 0 0 0 0 0 0 0 0 0
輸出文件名：maxflowb.out
10
【分析】
程序框架和沒有流量下限的最大流程序一樣（請參閱我以前的解題報告），只不過多了一個判斷而已。
只有每條邊上的殘餘容量大於等於 這條邊的流量下限並且大於等於 從遠點到當前點之間流量下限的最大值才滿足條件，也就是只有這樣，增廣路才能繼續往下擴展，否則直接跳出即可。
【我的代碼】

0001 #include <iostream>
0002 #include <cstdio>

0003 #include <cstdlib>
0004 #include <cstring>
0005 #include <queue>
0006 using namespace std;

0007 
0008 const int INF=0x7ffffff;
0009 const int MAXN=101;

0010 int LLimit[MAXN][MAXN]; /*Lower Limit*/
0011 int Map[MAXN][MAXN];
0012 int Father[MAXN];

0013 bool Used[MAXN];
0014 int Ans=0;
0015 int N;

0016 int S,T;
0017 
0018 void Ford_Fulkerson()
0019 {
0020     while(1)

0021     {
0022         queue<int>Q;/*Queue*/
0023         queue<int>MLL;/*Max Lower Limit*/

0024         memset(Used,0,sizeof(Used));
0025         memset(Father,0,sizeof(Father));
0026 
0027         int now;/*Now position*/

0028         Used[S]=true;
0029         Q.push(S);
0030         MLL.push(0);
0031         int LowerLimit;

0032         while(!Q.empty())
0033         {
0034             now=Q.front();
0035             LowerLimit=MLL.front();

0036             Q.pop();
0037             MLL.pop(); 
0038             if(now==T)
0039                 break;

0040             for (int i=1;i<=N;i++)/*i:Next Position*/
0041             {

0042                 if(Map[now][i] &&Map[now][i]>=LLimit[now][i] &&

0043                     Map[now][i]>=LowerLimit && !Used[i])
0044                 {
0045                     Father[i]=now;

0046                     Used[i]=true;
0047                     Q.push(i);
0048                     if(LLimit[now][i]>LowerLimit)

0049                         MLL.push(LLimit[now][i]);
0050                     else
0051                         MLL.push(LowerLimit);
0052                 }

0053             }
0054         }
0055 
0056         if(!Used[T])// There is no Augmenting Path.

0057             break;
0058 
0059         int u;
0060         int Min=INF;

0061         for (u=T;u!=S;u=Father[u])
0062         {
0063             if(Map[Father[u]][u]<Min)

0064                 Min=Map[Father[u]][u];
0065         }
0066 

0067         for (u=T;u!=S;u=Father[u])
0068         {
0069             Map[Father[u]][u]-=Min;

0070             Map[u][Father[u]]+=Min;
0071         }
0072 
0073         Ans+=Min;

0074     }
0075 }
0076 
0077 
0078 void init()

0079 {
0080     scanf("%d\n",&N);
0081     memset(Map,0,sizeof(Map));
0082 

0083     int v;
0084     for (int i=1;i<=N;i++)

0085     {
0086         for (int j=1;j<=N;j++)
0087         {

0088             scanf("%d",&v);
0089             LLimit[i][j]=v;
0090             scanf("%d",&v);

0091             Map[i][j]=v; 
0092         }
0093     }
0094     S=1;

0095     T=N; 
0096     return; 
0097 }
0098 

0099 int main()
0100 {
0101     freopen("maxflowb.in","r",stdin);
0102     freopen("maxflowb.out","w",stdout);

0103     init();
0104     Ford_Fulkerson();
0105     printf("%d\n",Ans);
0106     return 0;

0107 }