2144 数据结构实验之图论九：最小生成树

骑猪看日落 2022-06-04 07:10 162阅读 0赞

数据结构实验之图论九：最小生成树

Time Limit: 1000MS Memory Limit: 65536KB

#### Problem Description ####

有n个城市，其中有些城市之间可以修建公路，修建不同的公路费用是不同的。现在我们想知道，最少花多少钱修公路可以将所有的城市连在一起，使在任意一城市出发，可以到达其他任意的城市。

#### Input ####

输入包含多组数据，格式如下。

第一行包括两个整数n m，代表城市个数和可以修建的公路个数。(n <= 100， m <=10000)

剩下m行每行3个正整数a b c，代表城市a 和城市b之间可以修建一条公路，代价为c。

#### Output ####

每组输出占一行，仅输出最小花费。

#### Example Input ####

3 2
    1 2 1
    1 3 1
    1 0

#### Example Output ####

2
    0

#include<bits/stdc++.h>
    using namespace std;
    #define INF 0x3f3f3f3f
    int mmp[1010][1010];
    bool visit[1010];
    int lowcost[1010];
    int m,n;
    int sum,flag;
    void prime()
    {
        int k;
        int temp;
        visit[1]=true;
        for(int i=1;i<=m;i++)
            lowcost[i]=mmp[i][1];
        for(int i=2;i<=m;i++)
        {
            temp=INF;
            for(int j=1;j<=m;j++)
            {
                if(!visit[j]&&lowcost[j]<temp){
                    temp=lowcost[j];
                    k=j;
                }
            }
            /*if(temp==INF)
            {
                flag=1;
                break;
            }*/
            visit[k]=true;
            sum+=temp;
            for(int j=1;j<=m;j++)
            {
                if(!visit[j]&&lowcost[j]>mmp[j][k])
                    lowcost[j]=mmp[j][k];
            }
        }
    }
    int main()
    {
        int v,u,cost;
        while(cin>>m>>n)
        {
            memset(mmp,INF,sizeof(mmp));
            memset(visit,false,sizeof(visit));
            flag=0;
            sum=0;
            for(int i=0;i<n;i++)
            {
                cin>>v>>u>>cost;
                if(mmp[u][v]>cost)
                {
                    mmp[v][u]= mmp[u][v]= cost;
                }
            }
            prime();
            if(!flag)printf("%d\n",sum);
            //else printf("-1\n");
        }
    }