【題目描述】

城市C是一個(gè)非常繁忙的大都市，城市中的道路十分的擁擠，于是市長決定對其中的道路進(jìn)行改造。城市C的道路是這樣分布的：城市中有n個(gè)交叉路口，有些交叉路口之間有道路相連，兩個(gè)交叉路口之間最多有一條道路相連接。這些道路是雙向的，且把所有的交叉路口直接或間接的連接起來了。每條道路都有一個(gè)分值，分值越小表示這個(gè)道路越繁忙，越需要進(jìn)行改造。但是市政府的資金有限，市長希望進(jìn)行改造的道路越少越好，于是他提出下面的要求：

1．改造的那些道路能夠把所有的交叉路口直接或間接的連通起來。

2．在滿足要求1的情況下，改造的道路盡量少。

3．在滿足要求1、2的情況下，改造的那些道路中分值最大值盡量小。

作為市規(guī)劃局的你，應(yīng)當(dāng)作出最佳的決策，選擇那些道路應(yīng)當(dāng)被修建。

【輸入】

第一行有兩個(gè)整數(shù)n,m表示城市有n個(gè)交叉路口，m條道路。接下來m行是對每條道路的描述，u, v, c表示交叉路口u和v之間有道路相連，分值為c。(1≤n≤300，1≤c≤10000)。

【輸出】

兩個(gè)整數(shù)s, max，表示你選出了幾條道路，分值最大的那條道路的分值是多少。

【輸入樣例】

4 5
1 2 3
1 4 5
2 4 7
2 3 6
3 4 8

【輸出樣例】

3 6

【源程序】

#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 g[N][N]; int dis[N],vis[N]; int main() {int n,m;cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){if(i==j)g[i][j]=0;elseg[i][j]=INF;}for(int i=1;i<=m;i++){int x,y,w;cin>>x>>y>>w;g[x][y]=w;g[y][x]=w;}memset(vis,0,sizeof(vis));for(int i=1;i<=n;i++)dis[i]=g[1][i];for(int i=1;i<=n;i++){int k;int minn=INF;for(int j=1;j<=n;j++)if(!vis[j]&&dis[j]<minn){minn=dis[j];k=j;}vis[k]=1;for(int j=1;j<=n;j++)if(!vis[j]&&dis[j]>g[k][j])dis[j]=g[k][j];}int maxx=-INF;for(int i=1;i<=n;i++)maxx=max(maxx,dis[i]);cout<<n-1<<" "<<maxx<<endl;return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的繁忙的都市（信息学奥赛一本通-T1392）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。