洛谷 [SCOI2005] 繁忙的都市 题解

题目描述

城市C是一个非常繁忙的大都市,城市中的道路十分的拥挤,于是市长决定对其中的道路进行改造。城市C的道路是这样分布的:城市中有n个交叉路口,有些交叉路口之间有道路相连,两个交叉路口之间最多有一条道路相连接。这些道路是双向的,且把所有的交叉路口直接或间接的连接起来了。每条道路都有一个分值,分值越小表示这个道路越繁忙,越需要进行改造。但是市政府的资金有限,市长希望进行改造的道路越少越好,于是他提出下面的要求:

1.改造的那些道路能够把所有的交叉路口直接或间接的连通起来。

2.在满足要求1的情况下,改造的道路尽量少。

3.在满足要求1、2的情况下,改造的那些道路中分值最大的道路分值尽量小。

任务:作为市规划局的你,应当作出最佳的决策,选择那些道路应当被修建。

输入输出格式

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

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

输入输出样例

输入样例#1:

4 5
1 2 3
1 4 5
2 4 7
2 3 6
3 4 8
输出样例#1:

3 6

写了两种方法:
一种邻接表,一种邻接矩阵,都是Prim算法.

邻接表:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<iostream>
#include<cstring>
using namespace std;
int u[90001],v[90001],w[90001],first[301],_next[90001];
int lowcost[301];
int m,n;
int __max=0;
void prim(){
    memset(lowcost,10001,sizeof(lowcost));
    lowcost[1]=0;
    for(int e=first[1];e!=-1;e=_next[e])lowcost[v[e]]=w[e];
    for(int i=2;i<=n;i++){
        int min=10001,minid=0;
        for(int j=2;j<=n;j++){
            if(lowcost[j]<min&&lowcost[j]!=0){
                min=lowcost[j];
                minid=j;
            }
        }
        lowcost[minid]=0;
        if(__max<min)__max=min;
        for(int e=first[minid];e!=-1;e=_next[e]){
            if(w[e]<lowcost[v[e]])lowcost[v[e]]=w[e];
        }
    }
}
inline void insert_(int u1,int v1,int w1){
    static int i=0;
    u[i]=u1;v[i]=v1;w[i]=w1;
    _next[i]=first[u[i]];
    first[u[i]]=i;
    i++;
}
int main(){
    ios::sync_with_stdio(false);
    memset(first,-1,sizeof(first));
    cin>>n>>m;
    for(int i=0;i<m;i++){//邻接表是单向的,需要插入两次,不能忘!
        int u1,v1,w1;
        cin>>u1>>v1>>w1;
        insert_(u1,v1,w1);
        insert_(v1,u1,w1);
    }
    prim();
    cout<<n-1<<" "<<__max;
}

邻接矩阵:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
//Prim算法
#include<iostream>
#include<cstring>
#include<cstdlib>
#define Rep1(i,n) for(int i=1;i<=n;i++)
using namespace std;
int map[301][301];
int lowcost[301];
int __max=0;
int n,m;
void prim(){//从编号为1开始
    lowcost[1]=0;
    for(int i=2;i<=n;i++)lowcost[i]=map[1][i];
    for(int i=2;i<=n;i++){
        int min=10001;
        int minid=0;
        for(int j=2;j<=n;j++){
            if(lowcost[j]<min&&lowcost[j]!=0){
                min=lowcost[j];
                minid=j;
            }
        }
        if(__max<min)__max=min;
        lowcost[minid]=0;
        for(int j=2;j<=n;j++){
            if(lowcost[j]>map[minid][j]){
                lowcost[j]=map[minid][j];
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    Rep1(i,n)Rep1(j,n)map[i][j]=10001;
    Rep1(i,m){
        int u,v,w;
        cin>>u>>v>>w;
        map[u][v]=w;
        map[v][u]=w;
    }
    prim();
    cout<<n-1<<" "<<__max;
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注