BZOJ 1083: [SCOI2005]繁忙的都市

Hammer-cwz-77 2018-03-05 原文

Description

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

Input

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

Output

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

Sample Input

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

Sample Output

3 6

 1 /**************************************************************
 2     Problem: 1083
 3     User: Hammer_cwz_77
 4     Language: C++
 5     Result: Accepted
 6     Time:24 ms
 7     Memory:1880 kb
 8 ****************************************************************/
 9  
10 #include<iostream>
11 #include<cstdio>
12 #include<cstring>
13 #include<algorithm>
14 using namespace std; 
15 const int maxn = 309, maxm=50009;
16  
17 inline int read()
18 {
19     int x=0;char a=getchar();
20     while ( a<'0' || a>'9' )    a=getchar();
21     while ( a>='0' && a<='9'){
22         x=10*x+a-'0';    a=getchar();
23     }
24     return x;
25 }
26  
27 struct Point{
28     int u,v,w;
29 }e[maxm];
30 int n,m;int mx=0;
31 int f[maxn]={0};
32  
33 inline int find(int x)
34 {
35     return x==f[x] ? x:f[x]=find(f[x]);
36 }
37 //路径压缩形 的基本模板
38  
39 inline bool cmp(const Point &x,const Point &y)
40 {
41     return x.w<y.w;
42 }
43 
44  
45  
46  
47 void init()
48 {
49     n=read();    m=read();
50     for (int i = 1; i <= n; i++ )    
51         f[i]=i;
52     for (int i = 1; i <= m; i++)
53     {
54         e[i].u=read();
55         e[i].v=read();
56         e[i].w=read();
57     }
58 }
59  
60 inline bool merge(int u,int v)
61 {
62     int x=find(u);
63     int y=find(v);
64     if (  x!=y )
65     {
66         f[x]=y;
67         return true;
68     }
69     return false;
70 }
71 //判断 + 合并 
72  
73 void solve()
74 {
75     sort(e+1,e+m+1,cmp);
76     int cnt= 0; 
77     for (int i = 1; i <= m; i++)
78     {
79         if ( merge(e[i].u,e[i].v))
80         {
81             cnt++; 
82             if ( mx < e[i].w )
83                 mx = e[i].w;
84         }
85         if ( cnt==n-1 )    
86             break;
87     }
88 }
89 int main()
90 {
91     init();
92     solve();
93     printf("%d %d\n",n-1,mx);
94     return 0;
95 }