文章

25

粉丝

0

获赞

27

访问

1.4k

头像
Freckles 题解:Kruskal
P1183 北京大学上机题
发布于2026年2月22日 16:33
阅读数 55

#include <bits/stdc++.h>
using namespace std;
const int maxn=105;

struct edge{
    int u,v;
    double w;
}edges[maxn*maxn];
bool compare(edge a,edge b){
    return a.w<b.w;
}
struct freckle{
    double x,y;
};

int fa[maxn];
int find(int x){
    if(x==fa[x]) return x;
    fa[x]=find(fa[x]);
    return fa[x];
}

int n,m,t;
int main(){
    while(cin>>n&&n!=0){
        freckle freckles[n];
        m=n*(n-1)/2;
        double sum=0;
        for(int i=0;i<n;i++){
            fa[i]=i;
            cin>>freckles[i].x>>freckles[i].y;
        }
        int k=0;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                edges[k].u=i;
                edges[k].v=j;
                edges[k].w=sqrt(pow(freckles[i].x-freckles[j].x,2)+pow(freckles[i].y-freckles[j].y,2));
                k++;
            }
        }
        sort(edges,edges+m,compare);
        for(int i=0;i<m;i++){
   ...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发