题目描述

kruskal算法：当前已经循环完了第i条边，已经求出了由所有前i条边构成的连通块
更新思路为：cnt刚开始=n，意思为每个点都没进入集合，把每个点看成一个连通块，连通块数量为n。
每当合并a和b，cnt–，每合并一次，连通块数量-1

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>

using namespace std;

const int N=510;         

int p[N];
int n,k;
double res=0;
typedef pair<double,double> pii;
pii pos[N];

struct Edge
{
    int a,b;
    double w;

     bool operator< (const Edge &W)const
    {
        return w < W.w;
    }
}edge[N*N];



int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    else return x;
} 



int main()
{
    cin>>n>>k;
    //初始化
    for(int i=1;i<=n;i++)
    {
        p[i]=i;

    }
    for(int i=1;i<=n;i++)
    {
        cin>>pos[i].first>>pos[i].second;
    }
    int t=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            double x1=pos[i].first;
            double x2=pos[j].first;
            double y1=pos[i].second;
            double y2=pos[j].second;
            double w=(x1-x2)*(x1-x2) + (y1-y2)*(y1-y2);
            w=sqrt(w);
            edge[t++]={i,j,w};
        }
    }
    sort(edge+1,edge+t);
    //记录目前有几个连通块
    int cnt=n;
    //kruskal算法
    double res=0;
    for(int i=1;i<t;i++)
    {
        int a=edge[i].a;
        int b=edge[i].b;
        double w=edge[i].w;

        a=find(a);
        b=find(b);
        if(a!=b)
        {
            cnt--;
            p[a]=b;
        }
        if(cnt==k)
        {
            printf("%.2f",w);
            break;
        }
    }

    return 0;
}

二刷，注意判断结束条件，k==cnt

有k个连通块，相当于已经把k+1个点装入连通块，但是我们最多只能有k个点装入连通块，因此最后一条加入的边是不能被加入的，作为d输出

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>

using namespace std;

const int N=510;         

int p[N];
int n,k;
double res=0;
typedef pair<double,double> pii;
pii pos[N];

struct Edge
{
    int a,b;
    double w;

     bool operator< (const Edge &W)const
    {
        return w < W.w;
    }
}edge[N*N];


int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    else return x;
}

int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        p[i]=i;

    }
    //连通块个数cnt,初始为n
    int cnt=n;
    for(int i=1;i<=n;i++)
    {
        int a,b;
        cin>>a>>b;
        pos[i]={a,b};
    }
    int t=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            double x1=pos[i].first,y1=pos[i].second,x2=pos[j].first,y2=pos[j].second;
            edge[t].a=i;
            edge[t].b=j;
            edge[t].w=sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
            t++;
        }
    }
    sort(edge+1,edge+t);
    t--;
    int res=0;
    //开始做t条边的kruscal算法
    for(int i=1;i<=t;i++)
    {
        int a=edge[i].a;
        int b=edge[i].b;
        a=find(a);
        b=find(b);
        if(a!=b)
        {
            p[a]=b;
            cnt--;
        }
        // 有k个连通块，相当于已经把k+1个点装入连通块，但是我们最多只能有k个点装入连通块，因此最后一条加入的边是不能被加入的，作为d输出
        if(cnt==k)
        {
             printf("%.2f",edge[i].w);
             break;
        }

    }

    return 0;
}

kruscal求连通块，每加上一条边，连通块个数-1，到k个连通块时退出

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

const int N=510*510;

int n,k;
typedef pair<int,int> pii;
pii p[N];
int pa[N];

int find(int x)
{
    if(x!=pa[x]) pa[x]=find(pa[x]);
    return pa[x];
}

struct edge
{
    int a,b;
    double w;
    bool operator< (const edge &W) const
    {
        return w<W.w;
    }
}edges[N];

double get_dist(pii a,pii b)
{
    double x1=a.first,x2=b.first,y1=a.second,y2=b.second;
    return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
}

int main()
{
    cin>>n>>k;
    int cnt=n;
    for(int i=1;i<=n;i++)
    {
        cin>>p[i].first>>p[i].second;
        pa[i]=i;
    }

    int m=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<i;j++)
        {
            edges[++m]={i,j,get_dist(p[i],p[j])};
        }
    }

    sort(edges+1,edges+1+m);
    double res=0;
    double ans;
    for(int i=1;i<=m;i++)
    {
        int a=edges[i].a;
        int b=edges[i].b;
        double w=edges[i].w;

        a=find(a);
        b=find(b);
        if(a!=b)
        {
            pa[a]=b;
            cnt--;
            res=w;
            if(cnt<=k)
            {
                ans=res;
                break;
            }

        }
    }

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

    return 0;
}