GZOI2011 Rail 解題報告

第四題（40分）

提交文件：Rail.exe

輸入文件：Rail.in

輸出文件：Rail.out

題目描述：

你所在的省剛獲得國家撥款興建高鐵，高鐵的起止城市是國家選定的，中途可能經過若干城市。根據國家撥款的政策，國家將負擔費用最大的兩個區間，其餘的必須由省負擔。假如高鐵線路中途只經過一個城市，國家只負擔費用較大的區間。假如是直達的，國家將不負擔任何費用。

你被省裡選定作為這個項目的總工程師，你必須規劃出一條高鐵線路，使得省負擔的費用最少。當然，路線上每個城市最多只經過一次。

 

輸入格式（Rail.in）：

第一行是一個正整數n，n<=50，代表城市之間的高鐵建設費用估算（注意並非每對城市之間的建設費用都進行了估算）。接下來n行是用空格分隔的三個整數s,e,c。s和e代表城市的編碼，高鐵的起點和終點城市分別是編碼為0和1，其餘的城市依次編碼。c<=1000，是在s和e之間建設費用估算，從s到e與從e到s的建設費用是相同的。

輸出格式（Rail.out）：

輸出只有一行，格式為c1 c2 … cm cost，各數字用一個空格分隔，代表高鐵線路規劃和省負擔的費用。ci代表城市編碼（注意c1=0，cm=1），cost是費用。我們保證輸入肯定有解，如果有多個解，輸出當中經過城市最少的解，如果仍有多個解，則輸出當中按字典序排列最小的解。

樣例

Rail.in	Rail.out
7 0 2 10 0 3 6 2 4 5 3 4 3 3 5 4 4 1 7 5 1 8	0 3 4 1 3

【分析】

如圖，這就是樣例給的那個無向圖。我還以為要用什麼高級的最短路演算法呢，其實深度優先搜索都能過，而且很快！這數據量也太小了吧～～
我寫的是DFS，遞歸每個節點，搜尋最小花費。


【我的代碼】
裸代碼(Raw Code)

C++语言: Codee#25365

001 /*
002 *Problem: GZOI Rail
003 *Author: Yee-fan Zhu
004 *Email: zyfworks@gmail.com
005 */
006 #include <cstdio>
007 #include <cstdlib>
008 #include <iostream>
009 #include <vector>
010 using namespace std;
011
012 const int MAXN=53;
013 int Val[MAXN][MAXN];
014 int Map[MAXN][MAXN];
015 int N;
016
017 void init()
018 {
019     scanf("%d\n",&N);
020     int s,e,c;
021     for (int i=1;i<=N;i++)
022     {
023         scanf("%d %d %d\n",&s,&e,&c);
024         s++,e++;
025         Map[s][++Map[s][0]]=e;
026         Val[s][Map[s][0]]=c;
027        
028         Map[e][++Map[e][0]]=s;
029         Val[e][Map[e][0]]=c;
030     }
031 }
032
033 int Ans=0x7fffffff;
034
035 int Road[MAXN];
036 bool Used[MAXN];
037 vector<int>Res;
038
039 void Check(int First,int Second,int Total,int num)
040 {
041     int ans;
042     if(num==2)
043         ans=Total;
044     if(num==3)
045         ans=Total-First;
046     if(num>3)
047         ans=Total-First-Second;
048    
049     if(ans==Ans)
050     {
051         if(num>int(Res.size()))
052             return;
053         vector<int>::iterator iter;
054         iter=Res.begin();
055         bool flag=false;
056         for (unsigned int i=1;i<=Res.size();i++,iter++)
057         {
058             if(Road[i]<(*iter))
059             {
060                 flag=true;
061                 break;
062             }
063         }
064         if(!flag)
065             return;
066         Res.clear();
067         for (int i=1;i<=num;i++)
068             Res.push_back(Road[i]);
069     }
070    
071     if(ans<Ans)
072     {
073         Ans=ans;
074         Res.clear();
075         for (int i=1;i<=num;i++)
076             Res.push_back(Road[i]);
077     }
078 }
079
080 void dfs(int now,int First,int Second,int Total,int num)
081 {
082     if(Total-First-Second>Ans)
083         return;
084    
085     if(now==2)
086     {
087         Road[num]=now;
088         Check(First,Second,Total,num);
089         return;
090     }
091    
092     Used[now]=true;
093     Road[num]=now;
094    
095     for (int i=1;i<=Map[now][0];i++)
096     {
097         if(Used[Map[now][i]])
098             continue;
099         int tmp=Val[now][i];
100         int tmp1,tmp2;
101         if(tmp>First)
102         {
103             tmp1=tmp;
104             tmp2=First;
105         }
106        
107         if(tmp==First)
108         {
109             tmp1=First;
110             tmp2=First;
111         }
112        
113         if(tmp<First && tmp>Second)
114         {
115             tmp1=First;
116             tmp2=tmp;
117         }
118         if(tmp<=Second)
119         {
120             tmp1=First;
121             tmp2=Second;
122         }
123            
124         dfs(Map[now][i],tmp1,tmp2,Total+tmp,num+1);
125     }
126     Used[now]=false;
127 }
128
129
130 int main()
131 {
132     freopen("rail.in","r",stdin);
133     freopen("rail.out","w",stdout);
134     init();
135     dfs(1,0,0,0,1);
136    
137     vector<int>::iterator iter;
138     for (iter=Res.begin();iter!=Res.end();iter++)
139         printf("%d ",*iter-1);
140     printf("%d\n",Ans);
141     return 0;
142 }