D. Maximum Distance
题目链接：https://codeforces.com/contest/1081/problem/D
题意：
给出一个连通图以及一些特殊点，现在定义cost(u,v)为一条从u到v的路径上面边权的最大值，然后定义dis(u,v)为从u到v所有路径上面cost的最小值。
最后求所有特殊点到其它特殊点的最大距离...
题解：
这个题意似乎有点绕...
我们考虑一下最小生成树，那么点与点之间的距离就为最小生成树路径上面边权的最大值。
我们来证明一下：假设在最小生成树上面的路径cost为w1，另外在原图中还有一条路径从u到v，其cost为w2，那么必然有w2>w1的。那么我们最后的dis一定是w1。
那么我们现在的目标就是求特殊点到特殊点之间的最大距离。注意一下这里是从一个特殊点到其它所有特殊点的最大距离。
我们知道在Kruskal加边时，后加的边权一定时大于前面的边权的，既然要求最大权值，那么我们可以想加的最后一条边是否可以作为答案。
我们假设现在有两个集合，现在将其连接起来，当满足两个集合里面都有特殊点时我们就可以更新答案了，否则就不行。
所以我们合并的时候顺带维护一下集合里面特殊点的信息就可以了。
代码如下:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N =1e5+;
struct Edge{
int u,v,w;
bool operator < (const Edge&A)const{
return w<A.w;
}
}e[N];
int n,m,k;
int a[N],f[N],val[N];
int find(int x){
if(x==f[x]) return f[x];
f[x]=find(f[x]);
return f[x];
}
int main(){
cin>>n>>m>>k;
int tot=k;
for(int i=,t;i<=k;i++){
cin>>t;
a[t]=;
}
for(int i=;i<=m;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
e[i]=Edge{u,v,w};
}
for(int i=;i<=n;i++) f[i]=i;
sort(e+,e+m+);
int ans;
for(int i=;i<=m;i++){
int u=e[i].u,v=e[i].v,w=e[i].w;
int fx=find(u),fy=find(v);
if(fx==fy) continue;
f[fx]=fy;
if(a[u]) val[fx]++;if(a[v]) val[fy]++;
if(val[fx]&&val[fy]) ans=w;
val[fy]+=val[fx];
}
for(int i=;i<=k;i++) cout<<ans<<" ";
return ;
}