[最短路徑][二分答案]USACO Jan08 Silver 架設電話線 phoneline 解題報告

Title: 架設電話線【試題傳送門】

Input: phoneline.in

Output: phoneline.out

Time Limit: 1000 ms

Memory Limit: 16 MB

Level: ★★☆

Farmer John打算將電話線引到自己的農場，但電信公司並不打算為他提供免費服務。於是，FJ必須為此向電信公司支付一定的費用。

FJ的農場周圍分佈著N(1 <= N <= 1,000)根按1..N順次編號的廢棄的電話線杆，任意兩根電話線杆間都沒有電話線相連。一共P(1 <= P <= 10,000)對電話線杆間可以拉電話線，其餘的那些由於隔得太遠而無法被連接。

第i對電話線杆的兩個端點分別為A_i、B_i，它們間的距離為L_i (1 <= L_i <= 1,000,000)。資料中保證每對{A_i，B_i}最多隻出現1次。編號為1的電話線杆已經接入了全國的電話網絡，整個農場的電話線全都連到了編號 為N的電話線杆上。也就是說，FJ的任務僅僅是找一條將1號和N號電話線杆連起來的路徑，其餘的電話線杆並不一定要連入電話網絡。

經過談判，電信公司最終同意免費為FJ連結K(0 <= K < N)對由FJ指定的電話線杆。對於此外的那些電話線，FJ需要為它們付的費用，等於其中最長的電話線的長度（每根電話線僅連結一對電話線杆）。如果需要連 結的電話線杆不超過K對，那麼FJ的總支出為0。

請你計算一下，FJ最少需要在電話線上花多少錢。

程序名: phoneline

輸入格式:

• 第1行: 3個用空格隔開的整數：N，P，以及K

• 第2..P+1行: 第i+1行為3個用空格隔開的整數：A_i，B_i，L_i

輸入樣例 (phoneline.in):

5 7 1

1 2 5

3 1 4

2 4 8

3 2 3

5 2 9

3 4 7

4 5 6

輸入說明:

一共有5根廢棄的電話線杆。電話線杆1不能直接與電話線杆4、5相連。電話線杆5不能直接與電話線杆1、3相連。其餘所有電話線杆間均可拉電話線。電信公司可以免費為FJ連結一對電話線杆。

輸出格式:

• 第1行: 輸出1個整數，為FJ在這項工程上的最小支出。如果任務不可能完成，輸出-1

輸出樣例 (phoneline.out):

4

輸出說明:

FJ選擇如下的連結方案：1->3；3->2；2->5，這3對電話線杆間需要的電話線的長度分別為4、3、9。FJ讓電信公司提供那條長度為9的電話線，於是，他所需要購買的電話線的最大長度為4。

【分析】

這題讓我想了半天，老蛋疼了～

雖然題目已經提示了，是最短路問題，但一開始我總是想著如何把常用的單源最短路算法(Dijkstra/SPFA)變形從而直接求出最優解。但是，一直沒想出來（我真菜╮(￣▽￣)╭），最後只好二分可行解了。如何判定一個數是不是可行解：

如果一個數X是可行解，則圖中存在一條路徑，使得邊權大於這個數X的邊不超過K條。

重新建一個圖，把原圖中邊權大於X的邊的權值設為1，其他的邊的權值設為0。

然後求最短路，得到1->N的最短路徑長度為D。

判斷D與K的關係，若D>K，則X不是可行解，否則X為可行解。

就這樣，二分查找那個X的最小值即可。

【我的代碼】

裸代碼RawCode

C++语言: Codee#25394

001 /*
002 *USACO Jan08 Silver phoneline
003 *Author:Yee-fan Zhu
004 *Website: http://blog.yeefanblog.tk/
005 *Method: Binary Search  /  Shortest Path
006 */
007 #include <cstdio>
008 #include <cstdlib>
009 #include <iostream>
010 #include <vector>
011 #include <cstring>
012 using namespace std;
013 typedef vector<int> Vector;
014 const int MAX=1000000000;
015 const int MAXE=300000;
016 const int MINE=1;
017 const int MAXN=1001;
018 bool OK[MAXE];
019 int N,P,K;
020
021 class Graph
022 {
023 public:
024     Vector Line[MAXN];
025     Vector Value[MAXN];
026     void Clear()
027     {
028         for(int i=1;i<=N;i++)
029             Line[i].clear(),
030             Value[i].clear();
031     }
032 }Phone,Temp;
033
034 Graph ReCreate(Graph Patn,int X)
035 {
036     Graph temp;
037     for(int i=1;i<=N;i++)
038     {
039         for(unsigned int j=0;j<Patn.Line[i].size();j++)
040         {
041             if(Patn.Value[i][j]>X)
042             {
043                 temp.Line[i].push_back(Patn.Line[i][j]);
044                 temp.Value[i].push_back(1);
045                 continue;
046             }
047             if(Patn.Value[i][j]<=X)
048             {
049                 temp.Line[i].push_back(Patn.Line[i][j]);
050                 temp.Value[i].push_back(0);
051             }
052         }
053     }
054     return temp;
055 }
056
057 int GetShortestPath(Graph G)
058 {
059     int S=1;
060     bool flag[MAXN];
061     int dist[MAXN];
062     for (int i=1;i<=N;i++)
063     {
064         dist[i]=MAX;
065         flag[i]=false;
066     }
067     for (unsigned int i=0;i<G.Line[S].size();i++)
068         dist[G.Line[S][i]]=G.Value[S][i];
069    
070     dist[S]=0;
071     for (int i=2;i<=N;i++)
072     {
073         int tmp=MAX;
074         int u=S;
075         for(int j=1;j<=N;j++)
076         {
077             if(!flag[j] && dist[j]<tmp)
078             {
079                 u=j;
080                 tmp=dist[j];
081             }
082         }
083         flag[u]=1;
084        
085         for(unsigned int j=0;j<G.Line[u].size();j++)
086         {
087             if(!flag[G.Line[u][j]])
088             {
089                 int newdist=dist[u]+G.Value[u][j];
090                 if(newdist<dist[G.Line[u][j]])
091                 {
092                     dist[G.Line[u][j]]=newdist;
093                 }
094             }
095         }
096     }
097     return dist[N];
098 }
099
100 bool Check(int X)
101 {
102     Temp.Clear();
103     Temp=ReCreate(Phone,X);
104     int Res=GetShortestPath(Temp);
105     if(Res<=K)
106         return true;
107     return false;
108 }
109
110 void solve()
111 {
112     int l=0,r=MAXE,mid;
113     while(l+1<r)
114     {
115         mid=(l+r)/2;
116         int Res=Check(mid);
117         if(Res)
118         {
119             OK[mid]=true;
120             r=mid;
121             continue;
122         }
123         if(!Res)
124         {
125             l=mid;
126             continue;
127         }
128     }
129     if(r==MAXE)
130     {
131         printf("-1\n");
132         return;
133     }
134     if(r==MINE)
135     {
136         printf("0\n");
137         return;
138     }
139     if(OK[l])
140     {
141         printf("%d\n",l);
142         return;
143     }
144     if(OK[r])
145     {
146         printf("%d\n",r);
147         return;
148     }
149     return;
150 }
151
152 void init()
153 {
154     scanf("%d %d %d\n",&N,&P,&K);
155     int a,b,v;
156     for (int i=1;i<=P;i++)
157     {
158         scanf("%d %d %d\n",&a,&b,&v);
159         Phone.Line[a].push_back(b);
160         Phone.Value[a].push_back(v);
161         Phone.Line[b].push_back(a);
162         Phone.Value[b].push_back(v);
163     }
164 }
165
166 int main()
167 {
168     freopen("phoneline.in","r",stdin);
169     freopen("phoneline.out","w",stdout);
170     init();
171     solve();
172     return 0;
173 }