题解 CF1081D 【Maximum Distance】

是一道**最小生成树**的题目。 用的是 $kruskal$ 。 其他不多说，就讲一下为什么最后输出 $ans$ $k$ 次。 假设一个点到另一个点的最大值比现在小，那么其他的点也会走这条路。 所以上代码。 ```cpp #include<bits/stdc++.h> #define FOR(i,j,k) for(int i=(j);i<=(k);i++) using namespace std; int n,m,k,cnt; int ans; bool s[100001]; int f[100001]; struct point{ int a,b,val; }p[200001]; inline int read() { int x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } inline bool cmp(point x,point y) { return x.val<y.val; } int find(int x) { if(f[x]==x) return x; f[x]=find(f[x]); return f[x]; } int main() { n=read(),m=read(),k=read(); int x; for(int i=1;i<=n;i++) f[i]=i; for(int i=1;i<=k;i++) x=read(),s[x]=true; for(int i=1;i<=m;i++) { int u=read(),v=read(),w=read(); p[++cnt].a=u,p[cnt].b=v,p[cnt].val=w; } sort(p+1,p+1+cnt,cmp); for(int i=1;i<=cnt;i++) { int fa=find(p[i].a),fb=find(p[i].b); if(fa!=fb) { if(s[fa]&&s[fb]) ans=max(ans,p[i].val); if(s[fa]||s[fb]) s[fa]=s[fb]=1; f[fa]=fb; } } for(int i=1;i<=k;i++) printf("%d ",ans); return 0; } ```