嗯...
题目链接：https://www.luogu.org/problemnew/show/P2330
这道题的问法也实在是太模板了吧：
1.改造的道路越少越好
2.能够把所有的交叉路口直接或间接的连通起来
3.改造的那些道路中分值最大的道路分值尽量小
通过这些就可以判断出这是一道最小生成树的题（如果你还不了解最小生成树，请点击此网址查看：https://www.cnblogs.com/New-ljx/p/10779353.html）
思路：
就是一个最小生成树的模板，在最后将x点和y点合并的时候加上一个计数器cnt和一个maxn来保留最大值即可。
AC代码：
#include<cstdio>
#include<iostream>
#include<algorithm> using namespace std; int cnt, maxn;
int f[]; struct node{
int x, y, l;
} a[]; inline int cmp(node i, node j){
return i.l < j.l;
} inline int find(int x){
if(x != f[x])
f[x] = find(f[x]);
return f[x];
} int main(){
int n, m;
scanf("%d%d", &n, &m);
for(int i = ; i <= m; i++){
scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].l);
}
for(int i = ; i <= n; i++){
f[i] = i;
}
sort(a+, a++m, cmp);
for(int i = ; i <= m; i++){
int r1 = find(a[i].x);
int r2 = find(a[i].y);
if(r1 != r2){
f[r1] = r2;
cnt++;//计数器
maxn = max(maxn, a[i].l);//保存最大值
}
}
printf("%d %d", cnt, maxn);
return ;
}
AC代码