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

阳光穿透心脏的1/2处 2022-07-15 10:11 168阅读 0赞

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

Time Limit: 1000MS Memory Limit: 65536KB

[Submit][] [Statistic][]

#### 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 ####

Hint

此题是求最小生成树

#include<cstdio>
    #include<algorithm>
    using namespace std;
    
    int pre[2000];//记录顶点的根
    //用一个结构体来存放顶点跟道路长度
    struct node
    {
        int x;
        int y;
        int size;
    }road[1500];
    
    bool cmp(node a,node b)
    {
        return a.size<b.size;
    }
    
    //查找根节点
    int find(int x)
    {
        int r=x;
        while(pre[r]!=r)
        {
            r=pre[r];
        }
        int i,j;
        i=x;
        while(pre[i]!=r)
        {
            j=pre[i];
            pre[i]=r;
            i=j;
        }
        return r;
    }
    
    int main()
    {
        int n,m;//定点和道路
        while(~scanf("%d %d",&n,&m))
        {
            for(int i=1;i<=n;i++)
            {
                pre[i]=i;
            }
            for(int i=0;i<m;i++)
            {
                int a,b;
                scanf("%d %d %d",&road[i].x,&road[i].y,&road[i].size);
            }
            sort(road,road+m,cmp);//现将道路长度进行排序
            int sum=0;//记录道路总长
            int num=0;//记录累加的弧的个数
            int flag=0;//标记是否是连通图
            for(int i=0;i<m;i++)
            {
                if(find(road[i].x)!=find(road[i].y))
                {
                    pre[find(road[i].x)]=road[i].y;
                     sum+=road[i].size;
                     num++;
                }
                if(num==n-1)
                {
                    printf("%d\n",sum);
                    flag=1;//n个节点至少有n-1条弧才是连通图
                    break;
                }
            }
             if(flag==0)
             {
                printf("-1\n");
             }
        }
        return 0;
    }

[Submit]: http://www.sdutacm.org/onlinejudge2/index.php/Home/Contest/contestsubmit/cid/1907/pid/3362.html
[Statistic]: http://www.sdutacm.org/onlinejudge2/index.php/Home/Contest/conteststatus/cid/1907/pid/3362.html