PIPOJ 惠民工程(prim算法求最小生成树)

标签：居民点 index prim int 管道 惠民 PIPOJ ans

题目描述

市政府“惠民工程”的目标是在全市n个居民点间之架设煤气管道（但不一定有直接的管道相连，只要能间接通过管道可达即可）。很显然最多可架设 n(n-1)/2条管道,然而实际上要连通n个居民点只需架设n-1条管道就可以了。现请你编写程序，计算出该惠民工程需要的最低成本。

输入

测试输入包含若干测试用例。每个测试用例的第1行给出居民点数目M ( < =100 )、 评估的管道条数 N；随后的 N 行对应居民点间管道的成本，每行给出一对正整数，分别是两个居民点的编号，以及此两居民点间管道的成本（也是正整数）。为简单起见，居民点从1到M编号。

输出

对每个测试用例，在1行里输出全市管道畅通所需要的最低成本。若统计数据不足以保证畅通，则输出“?”。

样例输入

3 3
1 2 1
1 3 2
2 3 4
3 1
2 3 2

样例输出

3
?

#include<bits/stdc++.h>
using namespace std;
#define INF 0x7ffff
int a[105][105];
int vis[105];
int prim(int m,int n){//prim算法求最小生成树 
    int d[m];//存放到各个顶点的距离 
    int ans = 0;
    for(int i = 1; i <= m; i++){//初始化距离 
        d[i] = a[1][i];
    }
    vis[1] = 1; 
    for(int i = 2; i <= m; i++){//i=1开始不行，找m-1条边，需要m-1次循环，从1开始，则是m次循环 
        int min = INF;
        int index;
        for(int j = 1; j <= m; j++){
            if(!vis[j] && min > d[j]){
                min = d[j];
                index = j;
            }
        }
        if(min == INF){
            return -1;
        }
        vis[index] = 1;
        ans = ans + d[index];
        for(int j = 1; j <= m; j++){//更新距离 
            if(!vis[j] && d[j] > a[index][j]){
                d[j] = a[index][j];
            }
        }
    }
    return ans;
}
int main(){
    int m,n;
    while(scanf("%d%d",&m,&n)!=EOF){
        int x,y,z;
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= m; j++){
                if(i == j) a[i][j] = 0;
                else       a[i][j] = INF;
            } 
        }
        for(int i = 1; i <= m; i++){
            vis[i] = 0;
        }
        for(int i = 1; i <= n; i++){
            cin>>x>>y>>z;
            a[x][y]=a[y][x]=z;
        }
        int res = prim(m,n);
        if(res == -1) cout<<"?"<<endl;
        else          cout<<res<<endl;
    }
    return 0;
}

参考链接:(5条消息) 1004: 惠民工程_没被稻草压垮的骆驼的博客-CSDN博客

题目链接:PIPIOJ

标签：居民点,index,prim,int,管道,惠民,PIPOJ,ans
From： https://www.cnblogs.com/8023yyl/p/17054532.html