Avito Cool Challenge 2018 D. Maximum Distance (CF 1081D)

题目：Maximum Distance

题意：

给一张图，定义一条路径的长度为这条路径上的边权最大的边的边权。

定义两点间距离为这两点间路径的最小长度。

给出k个特殊节点，求对于每个特殊节点，距离它最远的点到它的距离。

思路：

可以知道，这个距离一定出现在最小生成树上。

所以先跑一遍kruskal，然后取第一个特殊节点dfs求出每个特殊节点到它的距离d[i]，所有节点的最远距离都是 max (d[i])。

代码：

#include<bits/stdc++.h>
using namespace std;#define read(x) scanf("%d",&x)
#define maxn 100000struct Edge{
    int x,y,z;Edge(int xx,int yy,int zz) {
    x=xx,y=yy,z=zz;}Edge(){
    }bool operator < (const Edge& oth) const {
    return z<oth.z;}};int n,m,K;
int sp[maxn+5];int fa[maxn+5];
int find(int x) {
    return fa[x]==0?x:fa[x]=find(fa[x]);
}vector<Edge> e;
vector<Edge> a[maxn+5];int d[maxn+5];void dfs(int x,int fa) {
    for(int i=0;i<a[x].size();i++) {
    int y=a[x][i].y;if(y==fa) continue;d[y]=max(d[x],a[x][i].z);dfs(y,x);}
}int main() {
    read(n),read(m),read(K);for(int i=1;i<=K;i++) {
    read(sp[i]);}for(int i=1;i<=m;i++) {
    Edge x;read(x.x),read(x.y),read(x.z);e.push_back(x);}sort(e.begin(),e.end());for(int i=0;i<m;i++) {
    int fa1=find(e[i].x),fa2=find(e[i].y);if(fa1!=fa2) {
    fa[fa1]=fa2;a[e[i].x].push_back(e[i]),a[e[i].y].push_back(Edge(e[i].y,e[i].x,e[i].z));}}dfs(sp[1],0);int max1=0;for(int i=1;i<=K;i++) {
    max1=max(max1,d[sp[i]]);}for(int i=1;i<=K;i++) {
    printf("%d ",max1);}return 0;
}