[CF1081D] Maximum Distance

给定 (n) 个点 (m) 条边的无向图，图中 (k) 个特殊顶点，你选定一个边集，使得 (k) 个点通过这些边能够连通，求选定边集中最长边的最小值。

Solution

显然在求最小生成树的时候维护一下就行了，关键是如何判定当前 (k) 个点已经连通

维护一个 (cnt)，如果本次合并涉及到的两个集合中都有特殊点，则 (cnt+1)

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1000005;

struct edge {
    int u,v,w;
    bool operator < (const edge &b) const {
        return w < b.w;
    }
} e[N];

int n,m,k,fa[N],fg[N],cnt,b[N],ans;

int find(int p) {
    return fa[p]==p?p:fa[p]=find(fa[p]);
}

void merge(int p,int q) {
    p=find(p); q=find(q);
    if(p-q) {
        fa[p]=q;
        fg[q]|=fg[p];
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin>>n>>m>>k;
    for(int i=1;i<=k;i++) {
        int t;
        cin>>t;
        b[t]=1;
    }
    for(int i=1;i<=m;i++) {
        cin>>e[i].u>>e[i].v>>e[i].w;
    }
    sort(e+1,e+m+1);
    for(int i=1;i<=n;i++) {
        fa[i]=i; fg[i]=b[i];
    }
    for(int i=1;i<=m;i++) {
        if(find(e[i].u)!=find(e[i].v)) {
            if(fg[find(e[i].u)] && fg[find(e[i].v)]) ++cnt;
            merge(e[i].u,e[i].v);
            ans=max(ans,e[i].w);
        }
        if(cnt==k-1) break;
    }
    for(int i=1;i<=k;i++) cout<<ans<<" ";
}