文章

1

粉丝

22

获赞

0

访问

319

头像
Prim构造最小生成树
P1341 浙江大学机试题
发布于2024年8月2日 00:29
阅读数 319

 

#include<iostream>
using namespace std;
const int INF = 1000000;
const int N = 105;

int g[N][N];
int v[N];
int n, m;

void func(){
    m = (n*(n-1))/2;
    for(int i=0;i<=n;i++){
        v[i] = INF;
    }
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            if(i == j){
                g[i][j] = 0;
            }else{
                g[i][j] = INF;
            }
        }
    }
    for(int i=0;i<m;i++){
        int u, v, w;
        cin>>u>>v>>w;
        g[u][v] = g[v][u] = w;
    }
    int sum = 0;
    v[1] = 0;
    for(int i=1;i<=n;i++){
        v[i] = g[1][i];
    }
    for(int k=1;k<n;k++){
        int min_p = -1;
        int min_w = INF;
        for(int i=1;i<=n;i++){
            if(v[i] < min_w && v[i] != 0){
                min_w = v[i];
                min_p = i;
            }
        }
        sum += min_w;
        for(int i=1;i<=n;i++){
        ...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发