kruscal wrong50 求助
查看原帖
kruscal wrong50 求助
302750
Main_WF楼主2021/7/15 20:16
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+10;

struct node{
	int u,v;
	double w;
	bool operator <(const node &t)
	{
		return w<t.w; 
	 } 
}e[maxn*maxn];
int k;

int n,c;
int x[maxn];
int y[maxn];
int f[maxn];

void add(int u,int v,double w)
{
	k++;e[k].u=u;e[k].v=v;e[k].w=w;
}

int find(int v)
{
	if(v!=f[v])f[v]=find(f[v]);
	return f[v];
}

void hb(int i,int j)
{
	int ri=find(i);
	int rj=find(j);
	f[ri]=rj;
}

double del(int i,int j)
{
	return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}

int main()
{
	
	cin>>n>>c;
	for(int i=1;i<=n;i++)
			cin>>x[i]>>y[i];
			
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			add(i,j,del(i,j));
	
	for(int i=1;i<=n;i++)f[i]=i;
	sort(e+1,e+1+k);
	
	int l=1;
	int v=n;
	while(v>c)
	{
		if(l==k+1)break;
		if(find(e[l].u)!=find(e[l].v))
		{
			hb(e[l].u,e[l].v);
			v--;
		}
		l++;
	 }
	 for(int i=l+1;i<=k;i++)
	 	if(find(e[i].u)!=find(e[i].v))
		 {
		 	printf("%.2f",e[i].w);
		 	break;
		 }
} 
2021/7/15 20:16
加载中...