網絡流入門試題 [最大流]運輸問題1 maxflowa

題目連結：http://cogs.yeefanblog.tk/t/11

Title: 运输问题1

Input: maxflowa.in

Output: maxflowa.out

Time Limit: 1000 ms

Memory Limit: 128 MB

Level: ★★☆

【问题描述】

    一个工厂每天生产若干商品，需运输到销售部门进行销售。从产地到销地要经过某些城镇，有不同的路线可以行走，每条两城镇间的公路都有一定的流量限制。请你计算，在不考虑其它车辆使用公路的前提下，如何充分利用所有的公路，使产地运输到销地的商品最多，最多能运输多少商品。

【输入格式】

输入文件有若干行
第一行，一个整数n，表示共有n个城市(2<=n<=100)
下面有n行,每行有n个数字。第p行第q列的数字表示城镇p与城镇q之间有无公路连接。数字为0表示无，大于0表示有公路，且该数字表示该公路流量。

【输出格式】

输出文件有一行
第一行，1个整数n，表示最大流量为n。

【输入输出样例】

输入文件名： maxflowa.in

6
0 4 8 0 0 0
0 0 4 4 1 0
0 0 0 2 2 0
0 0 0 0 0 7
0 0 0 6 0 9
0 0 0 0 0 0

输出文件名：maxflowa.out

8

【分析】

基礎的最大流問題。
由於源點沒有入度、匯點沒有出度，所以由樣例可以看出1號的源點，N號是匯點。
剩下就是用Ford-Fulkerson方法求解最大流即可。
《算法導論》上，Ford-Filkerson方法的偽代碼描述是：
FORD_FULKERSON(G,s,t)
1 for each edge(u,v)∈E[G]
2 do f[u,v] <— 0
3 f[v,u] <— 0
4 while there exists a path p from s to t in the residual network Gf
5 do cf(p) <— min{ cf(u,v) : (u,v) is in p }
6 for each edge(u,v) in p
7 do f[u,v] <— f[u,v]+cf(p)
8 f[v,u] <— -f[u,v]         

【我的代碼】

C++语言: Codee#25004

001 /*
002 *Problem:http://cogs.yeefanblog.tk/t/11
003 *Author:Yee-fan Zhu
004 *Website:http://www.zhuyf.tk/
005 *Method:網絡流 最大流 Full-Fulkerson
006 */
007 #include <iostream>
008 #include <cstdio>
009 #include <cstdlib>
010 #include <cstring>
011 #include <queue>
012 using namespace std;
013
014 const int INF=0x7ffffff;
015 const int MAXN=101;
016 int Map[MAXN][MAXN];
017 int Father[MAXN];
018 bool Used[MAXN];
019 int Ans;
020 int N,M;
021 int S,T;
022
023 void Ford_Fulkerson()
024 {
025     while(1)
026     {
027         queue<int>Q;
028         memset(Used,0,sizeof(Used));
029         memset(Father,0,sizeof(Father));
030
031         int now;
032         Used[S]=true;
033         Q.push(S);
034         while(!Q.empty())
035         {
036             now=Q.front();
037             Q.pop();
038             if(now==T)
039                 break;
040             for (int i=1;i<=N;i++)
041             {
042                 if(Map[now][i] && !Used[i])
043                 {
044                     Father[i]=now;
045                     Used[i]=true;
046                     Q.push(i);
047                 }
048             }
049         }
050
051         if(!Used[T])// There is no Augmenting Path.
052             break;
053
054         int u;
055         int Min=INF;
056         for (u=T;u!=S;u=Father[u])
057         {
058             if(Map[Father[u]][u]<Min)
059                 Min=Map[Father[u]][u];
060         }
061
062         for (u=T;u!=S;u=Father[u])
063         {
064             Map[Father[u]][u]-=Min;
065             Map[u][Father[u]]+=Min;
066         }
067
068         Ans+=Min;
069     }
070 }
071
072 void init()
073 {
074     scanf("%d\n",&N);
075     M=0;
076     memset(Map,0,sizeof(Map));
077
078     int v;
079     for (int i=1;i<=N;i++)
080     {
081         for (int j=1;j<=N;j++)
082         {
083             scanf("%d",&v);
084             Map[i][j]=v;
085             if(v)
086                 M++;
087         }
088     }
089     S=1;
090     T=N;
091     return;
092 }
093
094 int main()
095 {
096     freopen("maxflowa.in","r",stdin);
097     freopen("maxflowa.out","w",stdout);
098     init();
099     Ford_Fulkerson();
100     printf("%d\n",Ans);
101     return 0;
102 }