文章

2

粉丝

137

获赞

1

访问

11.5k

头像
易理解的题解
推荐阅读
P1311 浙江大学机试题
发布于2022年3月26日 18:53
阅读数 5.2k

先把道路修通状态为1的先合并一下。进行判断,如果边数达到N-1,说明道路都通了,则成本为0。如果部分没通,按照修路成本对所有的道路进行sort排序,把状态为0的合并一下,输出成本。

#include<bits/stdc++.h>
using namespace std;
const int MAX = 105;
int N,M;
int node[MAX];
int total,sum;
struct edge{
    int v1,v2;
    int w;
    int status;
}ed[MAX];

bool operator < (const edge&a,const edge&b){
    return a.w < b.w;
}

int findd(int x){
    if(x == node[x]){
        return x;
    }
    node[x] = findd(node[x]);
    return node[x];
}

void mergeV(int x,int y,int w,int status){
    int fx = findd(x);
    int fy = findd(y);
    if(fx != fy){
        node[fx] = fy;
        total++;
        if(status == 0){
            sum += w;
        }
        return;
    }
    else{
        return;
    }
}

int main(){
    while(scanf("%d",&N) != EOF){
        if(N == 0){
            break;
        }

        for(int i=1;i<=N;i++){
            node[i] = i;
        }

        M = N*(N-1)/2;
        total = 0;...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发