社区讨论
都是裸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 条回复,欢迎继续交流。
正在加载回复...