基站 题解

如果每个点都是基站，问题即求完全图最小生成树的最大边。

那么如果去掉原图中不是基站的点，即建一个新图，两个基站连一条边权为最短路的边，题目就变成上面的情况了。

因此可以考虑优化这个连边。设 表示离 最近的基站，跑多源最短路即可求出。那么对于一条边 ，如果 ，则在 和 间连一条边权为 的边即可。这样子正确性比较显然。

然后就是 Kruskal 的事了。

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,s,m,c[N];

struct edge { int v,w,nxt; } e[N<<1];
int head[N];
void addEdge(int u,int v,int w) {
    static int cnt=0;
    e[++cnt]=(edge){v,w,head[u]},head[u]=cnt;
}

struct node { int u,d; };
bool operator <(node a,node b) { return a.d>b.d; }
priority_queue<node> Q;
int dis[N],nr[N];
void dijkstra() {
    memset(dis,0x3f,sizeof(dis));
    for (int i=1;i<=s;++i)
        dis[c[i]]=0,nr[c[i]]=c[i],Q.push((node){c[i],0});
    while (!Q.empty()) {
        int u=Q.top().u,d=Q.top().d; Q.pop();
        if (d!=dis[u]) continue;
        for (int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v,w=e[i].w;
            if (dis[u]+w<dis[v])
                dis[v]=dis[u]+w,nr[v]=nr[u],Q.push((node){v,dis[v]});
        }
    }
}

int f[N];
int find(int x) { return x==f[x]?x:f[x]=find(f[x]); }
void merge(int x,int y) { x=find(x),y=find(y); if (x^y) f[x]=y; }

struct sedge { int u,v,w; } o[N<<1];
bool operator <(sedge a,sedge b) { return a.w<b.w; }
struct query { int u,v,w,id; } q[N];
bool operator <(query a,query b) { return a.w<b.w; }
int cnt=0;

int main() {
    n=read(),m=read();
    for (int i=1;i<=m;++i) {
        int u=read(),v=read(),w=read();
        addEdge(u,v,w),addEdge(v,u,w);
    }
    s=read();
    for (int i=1;i<=s;++i) c[i]=read();
    dijkstra();
    for (int u=1;u<=n;++u)
        for (int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v,w=e[i].w;
            if (nr[u]!=nr[v])
                o[++cnt]=(sedge){nr[u],nr[v],dis[u]+dis[v]+w};
        }
    sort(o+1,o+cnt+1);
    for (int i=1;i<=n;++i) f[i]=i;
    int ans=0;
    for (int i=1;i<=cnt;++i) {
        int u=o[i].u,v=o[i].v,w=o[i].w;
        if (find(u)!=find(v)) merge(u,v),ans=w;
    }
    printf("%d\n",ans);
    return 0;
}