讓我先把原題貼上來： 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，有點(diǎn)奇怪） Hint
Huge input,scanf is recommended. Source
POJ Contest,Author:Mathematica@ZSU 題目大意為:Flatopia島為促進(jìn)城市繁榮決定修高速路,這個(gè)島上有n個(gè)城市,要求修完路后,各城市之間可以相互到達(dá)（可以不必直接到達(dá)）,且修的總路程最短. 可以看出這是非常明顯的最小生成樹問題 為了多加練習(xí)，筆者在這里用了用了prim和Kruscal兩種方法分別解： 首先是prim算法（利用鄰接表和優(yōu)先隊(duì)列優(yōu)化）
#include<cstdio>#include<vector>#include<queue>#include<algorithm>#define MAX_V 501using namespace std;typedef pair<int,int> P;struct edge{int to,cost;//帶權(quán)的邊要用到結(jié)構(gòu)體表示; };struct cmp{ //自定義cmp比較函數(shù); 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];//因?yàn)橛玫氖青徑颖肀硎緢D，所以用到vector容器； bool used[MAX_V];//判斷所有的點(diǎn)（即城市）是否已加入集合; int prim(int V,int S){ priority_queue<P,vector<P>,cmp>que;//聲明一個(gè)按cmp方式從小到大排列的優(yōu)先隊(duì)列； fill(used,used+V+1,false);//一開始所有點(diǎn)都不在集合中，所以均初始化為false； int ans=0,flag=0;//flag用來計(jì)算加入集合的點(diǎn)個(gè)數(shù) que.push(P(0,S)); while(flag<V){ P p=que.top();que.pop(); int v=p.second; if(used[v]) continue;//如果隊(duì)列首部的點(diǎn)已經(jīng)加入過集合則跳過; used[v]=true;//否則將其加入集合并進(jìn)行下列操作; 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)); //若該點(diǎn)周圍有沒有加入集合的相鄰點(diǎn)，則將其加入優(yōu)先隊(duì)列 ； } } 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容器； }}這里用優(yōu)先隊(duì)列進(jìn)行prim算法優(yōu)化是《挑戰(zhàn)程序設(shè)計(jì)》一書中所提到的，不過書中并沒有相應(yīng)的代碼，在網(wǎng)上也搜索過無果所以只好自己瞎琢磨，不過根據(jù)自己寫的上面代碼，優(yōu)先隊(duì)列最多加入E（該題中是N*(N-1)）條邊，每次加入時(shí)更新用時(shí)O（log|V|）,因此總共用時(shí)為O（|E|log|V|）應(yīng)該沒錯(cuò)。
接下來看看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];//結(jié)構(gòu)體數(shù)組存放每條邊的信息； int par[MAX_V];//用來查詢每個(gè)頂點(diǎn)是否屬于同一連通流量的并查集數(shù)組; 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比較函數(shù)： 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)); }}非常明顯，該算法復(fù)雜度最高的部分就在于sort函數(shù)（快速排序）上，因此時(shí)間復(fù)雜度為 O(|E|log|E|）（E為邊的個(gè)數(shù)）； 可以看出，改進(jìn)后的prim算法和Kruskal在時(shí)間復(fù)雜度上差別實(shí)在不大，然而后者代碼比較容易理解，寫起來也簡(jiǎn)便一些（感覺我自己都不信@_@）,在都不會(huì)超時(shí)的情況下我比較推薦后者（講道理有一個(gè)超時(shí)的話另一個(gè)也好不到哪去吧……那時(shí)可能要用到斐波那契堆?……我還不會(huì)QAQ）。 總之，以上就是該題的解題報(bào)告，本人新手一個(gè)，請(qǐng)各位大佬發(fā)現(xiàn)有錯(cuò)的地方能夠加以指正，最好能提出一些意見和建議QWQ，也歡迎各位發(fā)表評(píng)論進(jìn)行提問討論。
新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
