游客 注册 | 登录
中文 | En

4026 - 繁忙的都市

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB
　　城市C是一个非常繁忙的大都市，城市中的道路十分的拥挤，于是市长决定对其中的道路进行改造。城市C的道路是这样分布的：城市中有n个交叉路口，有些交叉路口之间有道路相连，两个交叉路口之间最多有一条道路相连接。这些道路是双向的，且把所有的交叉路口直接或间接的连接起来了。每条道路都有一个分值，分值越小表示这个道路越繁忙，越需要进行改造。但是市政府的资金有限，市长希望进行改造的道路越少越好，于是他提出下面的要求：
l        改造的那些道路能够把所有的交叉路口直接或间接的连通起来。
l        在满足要求1的情况下，改造的道路尽量少。
l        在满足要求1、2的情况下，改造的那些道路中分值最大值尽量小。
【编程任务】
　　作为市规划局的你，应当作出最佳的决策，选择那些道路应当被修建。

题目输入

　　第一行有两个整数n,m表示城市有n个交叉路口，m条道路。接下来m行是对每条道路的描述，u, v, c表示交叉路口u和v之间有道路相连，分值为c。(1≤n≤300，1≤c≤10000)

题目输出

　　两个整数s, max，表示你选出了几条道路，分值最大的那条道路的分值是多少。

输入/输出样例

输入格式

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

输出格式

3 6

C语言解答

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int g[305][305];
int minn[305]; 
int start[305];  
int u[305];  
int n,e,total;

void prim(){
	int i,j,k;
    memset(minn,0x7f,sizeof(minn));
    minn[1] = 0; start[1]=0; 
    memset(u,1,sizeof(u));  
	for (i = 1; i <= n; i++)  
    {
        k = 0;
        for (j = 1; j <= n; j++) 
            if (u[j] && (minn[j] < minn[k]))
                k = j;
        u[k] = 0;                    
		total=total+minn[k];
        for (j = 1; j <= n; j++)
            if (u[j] &&(g[k][j]!=0) && (g[k][j] < minn[j]))
				{	minn[j] = g[k][j];  
					start[j]=k; 
				}
    } 
}

int main(){
	int i,j,w,t=0;
	scanf("%d%d",&n,&e);
    while (e>0) {
		scanf("%d%d%d",&i,&j,&w);
		g[i][j]=g[j][i]=w;
		e--;
	}
	prim();
    for (i = 1; i <= n; i++){ 
		if (minn[i]>t) t=minn[i];
	}
	printf("%d %d\n",n-1,t);
    return 0;
}
请先登陆