自动搬运

查看原文

来自洛谷，原作者为

	轻尘 **

搬运于2025-08-24 21:55:55，当前版本为作者最后更新于2018-04-21 15:39:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一道最小生成树的变式题，

不知道困了我多长时间，毕竟我太弱。

但作为一个蒟蒻，我还是要介绍一下我的做法。》》》

我们把每个点看成一个部落，每次取最小距离的两个抱团，同时部落也减少了一个....然后减减减，直到部落数==目标数，此时下一个不同部落的距离就是最短的距离！

是不是很好理解？

代码如下

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath> 
const int MA = 1e7;
using namespace std;
int o,n,k,num,flag;
int fa[MA];
inline int read()
{
    int x = 0;
    char c = getchar();
	while (!isdigit(c))c = getchar();
    while(c>='0'&&c<='9')
    {
        x = x*10+c-'0';
        c = getchar();
    }
    return x;
}
struct s
{
	int x,y;double l; 
}ass[MA],e[MA];//结构体存点； 

double cmp(s x,s y)
{	return x.l < y.l;}
//比较边长；
//
int find(int a)
{
	if(fa[a]!=a)
		fa[a] = find(fa[a]);
	return fa[a];
}
void unionn(int a,int b)
{	fa[find(b)] = find(a); }
//并查集；
void kruskal()
{
	for(int i=1;i<=o;i++)
	{
		if(num==n-k) flag = 1;
		if(find(e[i].x)!=find(e[i].y))
		{
			num++;
			unionn(e[i].x,e[i].y);
		if(flag){
			printf("%.2lf",e[i].l);
			return ;//写在里面，因为要不同的部落距离；
			}	
		}
	}
}
double measure(int a,int b)//求欧几里得距离
{
	return sqrt(pow((ass[a].x-ass[b].x),2)+pow((ass[a].y-ass[b].y),2));
}

int main()
{
    n = read(),k = read();
    for(int i=1;i<=n;i++)
        ass[i].x = read(),ass[i].y = read();
    o = 0;//边数；
    for(int i=1;i<=n;i++)
        for(int j=1;j<i;j++)
        {
            if(i!=j)e[++o].x=i,e[o].y=j,e[o].l=measure(i,j); //为所有的点建边；
        }
    for(int i=1;i<=n;i++)
    	fa[i] = i;
	sort(e+1,e+1+o,cmp);
//	for(int i=1;i<=o;i++)
//		cout<<e[i].l<<endl;
	kruskal();   
    return 0;
}

后记：

因为这种暴力的做法太朴素....

建边数是（n/2）*(n-1);

n = 1000时，o = ....499500;

好吧提交一下，

侥幸A过 : )