洛谷 P2330 [SCOI2005]繁忙的都市

题目传送门

解题思路:

本题就是一道最小生成树的模板题,求最小生成树中那条最大的边,边的数量就是n-1.

AC代码:

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm> 
 4 
 5 using namespace std;
 6 
 7 int n,m,fa[100001],ans;
 8 struct kkk {
 9     int from,to,v;
10 }e[100001];
11 
12 int find_father(int x) {
13     if(fa[x] == x) return x;
14     else return fa[x] = find_father(fa[x]);
15 }
16 
17 void Kruskal() {
18     for(int i = 1;i <= m; i++) {
19         int a = find_father(e[i].from);
20         int b = find_father(e[i].to);
21         if(a != b) {
22             ans = max(ans,e[i].v);
23             fa[a] = b;    
24         }
25     }
26 }
27 
28 bool cmp(kkk a,kkk b) {
29     return a.v < b.v;
30 }
31 
32 int main()
33 {
34     scanf("%d%d",&n,&m);
35     for(int i = 1;i <= m; i++)
36         scanf("%d%d%d",&e[i].from,&e[i].to,&e[i].v);
37     for(int i = 1;i <= n; i++)
38         fa[i] = i;
39     sort(e+1,e+m+1,cmp);
40     Kruskal();
41     printf("%d %d",n-1,ans);
42     return 0;
43 }