文章

9

粉丝

40

获赞

95

访问

3.8k

头像
继续畅通工程 题解:求助sos,为何通过率只有80%
P1311 浙江大学机试题
发布于2025年1月19日 13:57
阅读数 400

使用克鲁斯卡尔算法,输入过程中,当s==1时,直接合并,使用sort按权值从小到大排序,然后依次取出权值最小且没有修建的边,权值累加,有什么问题,求解答?

#include<bits/stdc++.h>

using namespace std;

const int N = 105;
int p[N];

struct EDGE{
    int a,b,w,s;
}edge[N*N];

bool cmp(EDGE e1,EDGE e2){
    return e1.w<e2.w;
}

int find(int x){
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}

int main(){
    int n,m;
    while(cin>>m){
        if(m==0) break;
        n = m*(m-1)/2;
        for(int i = 0;i < m;i ++) p[i] = i;

        for(int i = 0;i < n;i ++){
            int x,y,w,s;
            cin>>x>>y>>w>>s;
            if(s == 1){     //s==1,直接合并
                int a = find(x),b = find(y);
                if(a != b) p[a] = b;
            }
            edge[i] = {x,y,w,s};
        }
        sort(edge,edge+n,cmp);

        long long ans = 0;
        for(int i = 0;i < n;i ++){
            int a = edge[i].a,b = edge[i].b,w = edge[i].w,s = edge[i].s;
        ...
登录查看完整内容


登录后发布评论

1 条评论
快乐小土狗
2025年1月21日 12:04

for(int i = 0;i < m;i ++) p[i] = i;

看起来不太对劲

赞(0)