题目描述

如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。

输入格式

第一行包含两个整数 N,M，表示该图共有 N 个结点和 M 条无向边。

接下来M行，每行依次给出三个整数，为起点、终点、距离

输出格式

如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。

输入样例

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

输出样例

7

解法

代码

#include<iostream>

using namespace std;

int main(){
    //n为顶点数，m为要输入边数 ,sum为树的权值 
    int n=0,m=0,sum=0,max=0x7fffffff;
    //用邻接矩阵来存边的权值 
    int edge[5001][5001]={},set[5001]={0},dist[5001]={0x7fffffff};
    //读取数据 
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
                edge[i][j]=max;
        }
    int tempi=0,tempj=0,tempdis=0;
    for(int i=1;i<=m;i++){
            cin >> tempi >> tempj >> tempdis;
            if (edge[tempi][tempj] != 0 && edge[tempi][tempj] < tempdis)
                continue;
            edge[tempi][tempj] = tempdis;
            edge[tempj][tempi] = tempdis;
            } 
    //初始化prim算法
    set[1]=1;
    for(int i=1;i<=n;i++){
            dist[i]=edge[1][i];
            }
    //prim
    for(int i=2;i<=n;i++){
            //选最近的点 
            int tempv=0,tempdist=max;
            for(int j=1;j<=n;j++){
                    if(set[j]==0&&dist[j]<tempdist){
                          tempv=j;
                          tempdist=dist[j];
                          }
                    }
            //将点加入树种 
            set[tempv]=1;
            sum+=dist[tempv]; 
            //刷新距离
            for(int j=1;j<=n;j++){
                    if(set[j]==0&&edge[tempv][j]<dist[j])
                         dist[j]=edge[tempv][j];
                    }  
            }
    bool all=true;
    for(int i=1;i<=n;i++){
            if(set[i]==0)
               all=false;
            }
    if(all)
           cout<<sum;
    else   cout<<"orz";
    return 0;   
    }