文章

1

粉丝

0

获赞

1

访问

129

头像
kruskal:
P1183 北京大学上机题
发布于2024年3月19日 15:16
阅读数 129

kruskal算法套用

 

#include<bits/stdc++.h>
using namespace std;
struct node{
    double x,y;
}vec[105];
struct edg{
    int u,v;
    double len;
}edge[100*50];
int fa[105];
bool cmp(edg a,edg b){
    return a.len<b.len;
}
int find(int x){
    if(fa[x]==x)
        return x;
    fa[x]=find(fa[x]);
    return fa[x];
}
int main(){
    int n;
    while(cin>>n){
        for(int i=1;i<=n;i++){
            cin>>vec[i].x>>vec[i].y;
            fa[i]=i;
        }
        int len=n*(n-1)/2;
        int cnt=0;
        for(int i=1;i<n;i++){
            for(int j=i+1;j<=n;j++){
                edge[cnt].u=i;
                edge[cnt].v=j;
                edge[cnt++].len=sqrt(pow((vec[i].x-vec[j].x),2)+pow((vec[i].y-vec[j].y),2));
            }
        }
        sort(edge,edge+len,cmp);
        int sum=0;
        double res=0;
        for(int i=0;i<len;i++){
            int fu=find(edge[i].u);
            int fv...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发