【題目描述】

有一張城市地圖，圖中的頂點為城市，無向邊代表兩個城市間的連通關系，邊上的權為在這兩個城市之間修建高速公路的造價，研究后發(fā)現，這個地圖有一個特點，即任一對城市都是連通的。現在的問題是，要修建若干高速公路把所有城市聯系起來，問如何設計可使得工程的總造價最少？

【輸入】

n（城市數，1<≤n≤100）

e（邊數）

以下e行，每行3個數i,j,wij，表示在城市i,j之間修建高速公路的造價。

【輸出】

n-1行，每行為兩個城市的序號，表明這兩個城市間建一條高速公路。

【輸入樣例】

?5 8
1 2 2
2 5 9
5 4 7
4 1 10
1 3 12
4 3 6
5 3 3
2 3 8

【輸出樣例】

1 ?2
2 ?3
3 ?4
3 ?5

【源程序】

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<string> #include<cstdlib> #include<queue> #include<set> #include<map> #include<stack> #include<vector> #define INF 0x3f3f3f3f #define PI acos(-1.0) #define N 1001 #define MOD 123 #define E 1e-6 using namespace std; int father[N]; struct Node{int u;int v;int w; }g[N*N],dis[N]; void quick_sort(int left,int right) {int i=left,j=right;int mid=g[(left+right)/2].w;while(i<=j){while(g[i].w<mid)i++;while(g[j].w>mid)j--;if(i<=j){swap(g[i],g[j]);i++;j--;}}if(i<right)quick_sort(i,right);if(left<j)quick_sort(left,j); } int Find(int x) {if(father[x]==x)return x;return father[x]=Find(father[x]); } int Union(int x,int y) {x=Find(x);y=Find(y);if(x!=y){father[y]=x;return 1;}return 0; } int main() {int n,m;cin>>n>>m;for(int i=1;i<=n;i++)father[i]=i;for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;if(u>v)//小點在前swap(u,v);g[i].u=u;g[i].v=v;g[i].w=w;}int sum=0;quick_sort(1,m);for(int i=1;i<=m;i++)sum+=g[i].w;int cnt=0;for(int i=1;i<=m;i++)if(Union(g[i].u,g[i].v)){cnt++;dis[cnt].u=g[i].u;dis[cnt].v=g[i].v;dis[cnt].w=g[i].w;if(cnt==n-1)break;}for(int i=1;i<=cnt;i++)for(int j=i+1;j<=cnt;j++){if(dis[i].u>dis[j].u)swap(dis[i],dis[j]);else if(dis[i].u==dis[j].u&&dis[i].v>dis[j].v)swap(dis[i],dis[j]);}for(int i=1;i<=cnt;i++)cout<<dis[i].u<<" "<<dis[i].v<<endl;return 0; }

?

總結

以上是生活随笔為你收集整理的城市公交网建设问题（信息学奥赛一本通-T1348）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。