Arctic Network（洛谷）--北极通讯网络（loj）

洛谷传送门

loj传送门

一道蛮基础的最小生成树的题

题意也没绕什么圈子

只是叙述的有点累赘而已（loj上是这样的

也就读入加建边需要稍稍稍多想一下下

对于我这么一个蒟蒻

这是一道很好的板子题

（洛谷和loj上有一点点小不同，主要按loj的题面）

--------------------------------------------------------------------------------

（今日份懒得整题面qwq）

--------------------------------------------------------------------------------

k个村庄装上卫星设备后

可以把这k个村庄看成一个点

（这不是缩点qwq）

那么只需要求（n-k+1）个点和（n-k）条边所构成的最小生成树

kruskal一下

最后一次操作室加入生成树的边权就是最终答案

--------------------------------------------------------------------------------

显然有可能排序后

kruskal到的边不止（n-k）条

但是我比较emm...

就wawawa喽

--------------------------------------------------------------------------------

#include<cstdio>

#include<algorithm>

#include<iostream>

#include<cmath>

using namespace std;

inline int read()

{

    int sum = ,p = ;

    char ch = getchar();

    while(ch < '' || ch > '')

    {

        if(ch == '-')

            p = -;

        ch = getchar();

    }

    while(ch >= '' && ch <= '')

    {

        (sum *= ) += ch - '';

        ch = getchar();

    }

    return sum * p;

}

int n,k,cnt,tot;

double ans;

int x[],y[],fa[];

struct edge

{

    int l,r;

    double wei;

}e[];

double getdis(int x1,int y1,int x2,int y2)

{

    return (double) sqrt((double)(x1 - x2)*(x1 - x2) + (double)(y1 - y2) * (y1 - y2));

}

int findfa(int o)

{

    if(o == fa[o])

        return o;

    else

        return fa[o] = findfa(fa[o]);

}

int cmp(edge a,edge b)

{

    return a.wei < b.wei;

}

void kruskal()

{

    int u,v,mrk = ;

    sort(e+,e+cnt+,cmp);

    for(int i = ;i <= cnt;i++)

    {

        u = findfa(e[i].l);

        v = findfa(e[i].r);

        if(u == v)

            continue;

        fa[u] = v;

        mrk++;

        if(mrk == n - k)

        {

            ans = e[i].wei;

            break;

        }

    }

}

int main()

{

    n = read(),k = read();

    if(k >= n)

    {

        printf("0.00");

        return ;

    }

    if(k == )

        k = ;

    for(int i = ; i <= n; i++)

        x[i] = read(),y[i] = read();

    for(int i = ; i <= n; i++)

        for(int j = i + ; j <= n; j++)

        {

            cnt++;

            e[cnt].l = i;

            e[cnt].r = j;

            e[cnt].wei = getdis(x[i],y[i],x[j],y[j]);

        }

    for(int i = ;i <= n;i++)

        fa[i] = i;

    kruskal();

    printf("%.2lf",ans);

    return ;

}