[Time Gate]
https://www.luogu.org/problemnew/show/P2330
【解题思路】
与前几道题思路类似，就不过多赘述了
简单说明：
把交叉路口看做图中的点，道路为边，则可以从三个条件：
1．改造的那些道路能够把所有的交叉路口直接或间接的连通起来。
2．在满足要求1的情况下，改造的道路尽量少。
3．在满足要求1、2的情况下，改造的那些道路中分值最大的道路分值尽量小。
可得，本题是一个裸的最小生成树。
【code】
1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 using namespace std; 5 int n,m,u,v,c,ans=-1<<30,cnt; 6 int fa[50005]; 7 struct Node{ 8 int u; 9 int v; 10 int c; 11 }a[50005]; 12 inline int Find(int x){ 13 if(fa[x]!=x)fa[x]=Find(fa[x]); 14 return fa[x]; 15 } 16 inline void Union(int x,int y){ 17 int f1,f2; 18 f1=Find(x),f2=Find(y); 19 if(f1!=f2)fa[f1]=f2; 20 return ; 21 } 22 inline bool cmp(const Node &a,const Node &b){ 23 return a.c<b.c; 24 } 25 int main(){ 26 //freopen("2330.in","r",stdin); 27 //freopen("2330.out","w",stdout); 28 scanf("%d%d",&n,&m); 29 for(register int i=1;i<=m;i++) 30 scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].c); 31 for(register int i=1;i<=n;i++) 32 fa[i]=i; 33 sort(a+1,a+m+1,cmp); 34 for(register int i=1;i<=m;i++){ 35 if(Find(a[i].u)!=Find(a[i].v)){ 36 Union(a[i].u,a[i].v); 37 if(ans<a[i].c)ans=a[i].c; 38 cnt++; 39 } 40 } 41 printf("%d %d\n",cnt,ans); 42 return 0; 43 }