社区讨论
为啥一直40!求解!
P1991无线通讯网参与者 3已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @mi4eqmwn
- 此快照首次捕获于
- 2025/11/18 18:05 4 个月前
- 此快照最后确认于
- 2025/11/18 18:05 4 个月前
CPP
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
const int N=1005;
const int M=10005;
int f[N],x[N],y[N];
double ans;
struct edge
{
int u,v;
double w;
}E[M];
int find(int x)
{
if (f[x]==x) return x;
return f[x]=find(f[x]);
}
bool cmp(edge e1,edge e2)
{
return e1.w<e2.w;
}
bool cmpp(edge e1,edge e2)
{
return e1.w>e2.w;
}
int num=0;
void work(int i,int j)
{
num++;
int xx=x[j]-x[i],yy=y[j]-y[i];
E[num].u=i; E[num].v=j;
E[num].w=sqrt(xx*xx+yy*yy);
}
int n,m,k=0,t=0;
void kruskal()
{
for (int i=1; i<=n; i++) f[i]=i;
sort(E+1,E+num+1,cmp);
for (int i=1; i<=num; i++)
{
int xx=find(E[i].u),yy=find(E[i].v);
if (xx!=yy)
{
f[xx]=yy;
ans=E[i].w;
k++;
}
if (k==n-m) break;
}
printf("%.2f\n",ans);
}
void solve()
{
scanf("%d%d",&m,&n);
if (m>=n)
{
printf("0.00\n"); return ;
}
for (int i=1; i<=n; i++) scanf("%d%d",&x[i],&y[i]);
for (int i=1; i<=n; i++)
for (int j=i+1; j<=n; j++) work(i,j);
kruskal();
}
int main()
{
solve();
return 0;
}
回复
共 3 条回复,欢迎继续交流。
正在加载回复...