社区讨论

都是裸Kruskal,为什么我T了一个点

P2212[USACO14MAR] Watering the Fields S参与者 9已保存回复 12

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
12 条
当前快照
1 份
快照标识符
@mi85uclg
此快照首次捕获于
2025/11/21 09:07
4 个月前
此快照最后确认于
2025/11/21 09:45
4 个月前
查看原帖
RT
代码如下
CPP
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,c,f[2001],xy[2001][2],m=1,cnt;
long long ans;
int getf(int v){return f[v]==v?v:getf(f[v]);}
struct tube
{
	int u,v,w;
}e[2000001];
bool cmp(tube a,tube b){return a.w<b.w;}
int read()
{
	char c=getchar();
	int x=0,f=1;
	while(!isdigit(c))
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c))
	{
		x=x*10+c-48;
		c=getchar();
	}
	return x*f;
}
int main()
{
	scanf("%d%d",&n,&c);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&xy[i][0],&xy[i][1]);
		f[i]=i;
	}
	for(int i=1;i<=n;i++)
	    for(int j=i+1;j<=n;j++)
	    {
	    	int t=(xy[i][0]-xy[j][0])*(xy[i][0]-xy[j][0])+(xy[i][1]-xy[j][1])*(xy[i][1]-xy[j][1]);
	    	if(t<c) continue;
	        e[m].u=i;
	        e[m].v=j;
	        e[m].w=t;
	        m++;
	    }
	sort(e+1,e+1+m,cmp);
	for(int i=1;i<=m;i++)
	{
		int t1=getf(e[i].u);
		int t2=getf(e[i].v);
		if(t1==t2) continue;
		f[t2]=t1;
		ans+=e[i].w;
		if(++cnt==n-1)
		{
			printf("%lld",ans);
			return 0;
		}
	}
	printf("-1");
	return 0;
}
难不成要加特判?

回复

12 条回复,欢迎继续交流。

正在加载回复...