是一道最小生成树的题目。
用的是 \(kruskal\) 。
其他不多说,就讲一下为什么最后输出 \(ans\) \(k\) 次。
假设一个点到另一个点的最大值比现在小,那么其他的点也会走这条路。
所以上代码。
#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;
}