3362 数据结构实验之图论六：村村通公路

我会带着你远行 2022-06-04 06:44 160阅读 0赞

Time Limit: 1000MSMemory Limit: 65536KB

#### Problem Description ####

当前农村公路建设正如火如荼的展开，某乡镇政府决定实现村村通公路，工程师现有各个村落之间的原始道路统计数据表，表中列出了各村之间可以建设公路的若干条道路的成本，你的任务是根据给出的数据表，求使得每个村都有公路连通所需要的最低成本。

#### Input ####

连续多组数据输入，每组数据包括村落数目N(N <= 1000)和可供选择的道路数目M(M <= 3000)，随后M行对应M条道路，每行给出3个正整数，分别是该条道路直接连通的两个村庄的编号和修建该道路的预算成本，村庄从1～N编号。

#### Output ####

输出使每个村庄都有公路连通所需要的最低成本，如果输入数据不能使所有村庄畅通，则输出-1，表示有些村庄之间没有路连通。

#### Example Input ####

5 8
    1 2 12
    1 3 9
    1 4 11
    1 5 3
    2 3 6
    2 4 9
    3 4 4
    4 5 6

#### Example Output ####

#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;
                mmp[v][u]= mmp[u][v]= cost;
            }
            prime();
            if(!flag)printf("%d\n",sum);
            else printf("-1\n");
        }
    }