社区讨论

为啥一直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 条回复,欢迎继续交流。

正在加载回复...