[網絡最大流]POI1999 洞穴探險 gro 解題報告

問題描述

古老的Byte山上有一處神祕的連環洞穴。考古學家們爲了對這個洞穴進行研究，組織了一次探險活動。他們花了幾天的時間仔細地翻閱了前人留下的資料，對該連環洞穴有了大致的瞭解。

這是一個有許多不同的小溶洞組成的連環洞穴，每個小溶洞都分佈在不同的地層中，並且可能通過洞穴隧道與其他小溶洞相通。

考古學家們已經發現了作爲連環洞穴的入口的一個小溶洞，並且根據前人的資料，繪製出了洞穴的地圖，標明瞭哪些小溶洞之間是有洞穴隧道相連的。

富有冒險和激情的考古學家們都期望自己能夠獨自進行探險活動。於是，他們又提出了這樣的要求：從入口的溶洞出發時，每個人都選擇一條不同的 洞穴隧道前進；探險結束時，每個人都是通過不同的洞穴隧道抵達最底層的小溶洞。當然了，這些考古學家也達成了妥協：在探險的過程中，可以有不止一名的考古 學家通過同一條洞穴隧道。 爲了體現這次探險活動的一往直前的精神，考古學家們還決定，要從小溶洞入口進入，一直抵達最底層的溶洞！每個考古學家探險路線上通過的小溶洞所在的地層必 須比該路線上前一個溶洞的地層低。

考古學家提出來如此多的要求使得本次探險活動的組織者犯了愁，他究竟最多能邀請多少位考古學家來參加這項活動呢？



輸入文件

第一行是一個數N（2<=N<=200)

以下共有N-1行，第i+1行表示的是標號爲i個溶洞與哪些溶洞相連。每行第一個數字是Mi，表示共與Mi個溶洞相連，隨後是Mi個數字，爲這些溶洞的標號。

輸出文件

輸出文件只有一行，爲一個整數，表示的是最多能有多少位考古學家參加這次活動。

樣例輸入

12
4 3 4 2 5
1 8
2 9 7
2 6 11
1 8
2 9 10
2 10 11
1 12
2 10 12
1 12
1 12
該數據描述的是下面這樣一個連環洞穴：

样例输出
3

【分析】
讀題可知，這是一個明顯的網絡最大流問題。
由題目中的條件“從入口的溶洞出發時，每個人都選擇一條不同的 洞穴隧道前進；探險結束時，每個人都是通過不同的洞穴隧道抵達最底層的小溶洞” 可知，從源點流出的和流向匯點的邊的邊權都為1；
由“可以有不止一名的考古 學家通過同一條洞穴隧道”可知，洞穴中間的邊權為正無窮。

構圖後就剩下裸最大流了～由於節點個數僅有200個，所以一般的網絡最大流算法都可滿足要求。我寫的 Ford-Folkerson。

【我的代碼】
裸代碼

C++语言: Codee#25229

001 /*
002 *Problem: POI 1999 gro
003 *Author: Yee-fan Zhu
004 *Website:http://blog.yeefanblog.tk/
005 *Method: MaxFlow
006 */
007 #include <iostream>
008 #include <cstdio>
009 #include <queue>
010 #include <cstring>
011 #include <cstdlib>
012 using namespace std;
013
014 const int INF=0x7fffffff;
015 const int MAXN=202;
016 int Map[MAXN][MAXN];
017 int Father[MAXN];
018 bool Used[MAXN];
019 int S,T; /*S:Source; T:Sink*/
020 int N;
021 int Ans=0;
022
023 void Init_Graph()
024 {
025     scanf("%d\n",&N);
026    
027     S=1,T=N;
028     int Tmp,num;
029    
030     /*Read the No.1*/
031     scanf("%d",&Tmp);
032     for (int i=1;i<=Tmp;i++)
033     {
034         scanf("%d ",&num);
035         Map[1][num]=1;
036     }
037    
038     for (int i=2;i<=N-1;i++)
039     {
040         scanf("%d\n",&Tmp);
041         for(int j=1;j<=Tmp;j++)
042         {
043             scanf("%d\n",&num);
044            
045             if(num==N)
046                 Map[i][num]=1;
047             else
048                 Map[i][num]=INF;
049         }
050     }
051 }
052
053 void Ford_Fulkerson()
054 {
055     while(1)
056     {
057         queue<int>Q;
058         memset(Father,0,sizeof(Father));
059         memset(Used,false,sizeof(Used));
060         int now;
061         Used[S]=true;
062         Q.push(S);
063        
064         while(!Q.empty())
065         {
066             now=Q.front();
067             Q.pop();
068             if(now==T)
069                 break;
070             for (int i=1;i<=N;i++)
071             {
072                 if(Map[now][i] && !Used[i])
073                 {
074                     Father[i]=now;
075                     Used[i]=true;
076                     Q.push(i);
077                 }
078             }
079         }
080        
081         if(!Used[T])
082             break;
083        
084         int u;
085         int Min=INF;
086         for (u=T;u!=S;u=Father[u])
087         {
088             if(Map[Father[u]][u]<Min)
089                 Min=Map[Father[u]][u];
090         }
091        
092         for (u=T;u!=S;u=Father[u])
093         {
094             Map[Father[u]][u]-=Min;
095             Map[u][Father[u]]+=Min;
096         }
097        
098         Ans+=Min;
099     }
100    
101     printf("%d\n",Ans);
102 }
103
104 int main()
105 {
106     freopen("gro.in","r",stdin);
107     freopen("gro.out","w",stdout);
108     Init_Graph();
109     Ford_Fulkerson();
110     return 0;
111 }