讓我先把原題貼上來： Highways Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 27912 Accepted: 12734 Description
The island nation of Flatopia is perfectly flat. Unfortunately, Flatopia has no public highways. So the traffic is difficult in Flatopia. The Flatopian government is aware of this PRoblem. They’re planning to build some highways so that it will be possible to drive between any pair of towns without leaving the highway system.
Flatopian towns are numbered from 1 to N. Each highway connects exactly two towns. All highways follow straight lines. All highways can be used in both directions. Highways can freely cross each other, but a driver can only switch between highways at a town that is located at the end of both highways.
The Flatopian government wants to minimize the length of the longest highway to be built. However, they want to guarantee that every town is highway-reachable from every other town. Input
The first line of input is an integer T, which tells how many test cases followed. The first line of each case is an integer N (3 <= N <= 500), which is the number of villages. Then come N lines, the i-th of which contains N integers, and the j-th of these N integers is the distance (the distance should be an integer within [1, 65536]) between village i and village j. There is an empty line after each test case. Output
For each test case, you should output a line contains an integer, which is the length of the longest road to be built such that all the villages are connected, and this value is minimum. Sample Input
1
3 0 990 692 990 0 179 692 179 0 Sample Output
692（我看到的原題給的答案是 692，但我自己手算以及兩種方法算的都是871，有點奇怪） Hint
Huge input,scanf is recommended. Source
POJ Contest,Author:Mathematica@ZSU 題目大意為:Flatopia島為促進城市繁榮決定修高速路,這個島上有n個城市,要求修完路后,各城市之間可以相互到達（可以不必直接到達）,且修的總路程最短. 可以看出這是非常明顯的最小生成樹問題 為了多加練習，筆者在這里用了用了prim和Kruscal兩種方法分別解： 首先是prim算法（利用鄰接表和優先隊列優化）
#include<cstdio>#include<vector>#include<queue>#include<algorithm>#define MAX_V 501using namespace std;typedef pair<int,int> P;struct edge{int to,cost;//帶權的邊要用到結構體表示; };struct cmp{ //自定義cmp比較函數; bool Operator()(P a,P b){ if(a.first==b.first) return a.second>b.second; return a.first>b.first; }};vector<edge>G[MAX_V];//因為用的是鄰接表表示圖，所以用到vector容器； bool used[MAX_V];//判斷所有的點（即城市）是否已加入集合; int prim(int V,int S){ priority_queue<P,vector<P>,cmp>que;//聲明一個按cmp方式從小到大排列的優先隊列； fill(used,used+V+1,false);//一開始所有點都不在集合中，所以均初始化為false； int ans=0,flag=0;//flag用來計算加入集合的點個數 que.push(P(0,S)); while(flag<V){ P p=que.top();que.pop(); int v=p.second; if(used[v]) continue;//如果隊列首部的點已經加入過集合則跳過; used[v]=true;//否則將其加入集合并進行下列操作; ans+=p.first; flag++; for(int i=0;i<G[v].size();i++){ edge e=G[v][i]; if(!used[e.to]) que.push(P(e.cost,e.to)); //若該點周圍有沒有加入集合的相鄰點，則將其加入優先隊列 ； } } return ans;}int main(){ int T; scanf("%d",&T); while(T--){ int n,d; edge s,t; scanf("%d",&n); for(int i=1;i<=n;i++){//輸入圖形; for(int j=1;j<=n;j++){ scanf("%d",&d); if(i==j) continue; s.to=j,s.cost=d; t.to=i,t.cost=d; G[i].push_back(s); G[j].push_back(t); } } printf("%d/n",prim(n,1)); for(int i=1;i<=n;i++) G[i].clear();//最后一定要清空vector容器； }}這里用優先隊列進行prim算法優化是《挑戰程序設計》一書中所提到的，不過書中并沒有相應的代碼，在網上也搜索過無果所以只好自己瞎琢磨，不過根據自己寫的上面代碼，優先隊列最多加入E（該題中是N*(N-1)）條邊，每次加入時更新用時O（log|V|）,因此總共用時為O（|E|log|V|）應該沒錯。
接下來看看Kruskal算法
#include<cstdio>#include<algorithm>#define MAX_E 250000#define MAX_V 501using namespace std;struct edge{int fm,to,cost;};edge es[MAX_E];//結構體數組存放每條邊的信息； int par[MAX_V];//用來查詢每個頂點是否屬于同一連通流量的并查集數組; void init(int v){ for(int i =1;i<=v;i++) par[i]=i;}int find(int x){ if(par[x]==x) return x; return par[x]=find(par[x]);}bool same(int i,int j){ return find(i)==find(j);}void unite(int i,int j){ i=find(i),j=find(j); par[j]=i;}bool cmp(const edge& e1,const edge& e2){//自定義cmp比較函數： return e1.cost<e2.cost;}int Kruskal(int n){ sort(es,es+n*(n-1),cmp);//按es[i].cost的大小由小到大排序; init(n);//初始化并查集 int ans=0; for(int i=0;i<n*(n-1);i++){ edge e=es[i]; if(!same(e.fm,e.to)){ unite(e.fm,e.to); ans+=e.cost; } } return ans;}int main(){ int T; scanf("%d",&T); while(T--){ int n; scanf("%d",&n); int d; int k=0; for(int i=1;i<=n;i++){//輸入每條邊的信息; for(int j=1;j<=n;j++){ scanf("%d",&d); if(i==j) continue; es[k].fm=i,es[k].to=j,es[k].cost=d; k++; } } printf("%d/n",Kruskal(n)); }}非常明顯，該算法復雜度最高的部分就在于sort函數（快速排序）上，因此時間復雜度為 O(|E|log|E|）（E為邊的個數）； 可以看出，改進后的prim算法和Kruskal在時間復雜度上差別實在不大，然而后者代碼比較容易理解，寫起來也簡便一些（感覺我自己都不信@_@）,在都不會超時的情況下我比較推薦后者（講道理有一個超時的話另一個也好不到哪去吧……那時可能要用到斐波那契堆?……我還不會QAQ）。 總之，以上就是該題的解題報告，本人新手一個，請各位大佬發現有錯的地方能夠加以指正，最好能提出一些意見和建議QWQ，也歡迎各位發表評論進行提問討論。
新聞熱點
疑難解答
圖片精選
