图结构练习——最小生成树

刺骨的言语ヽ痛彻心扉 2022-08-10 06:11 156阅读 0赞

## 图结构练习——最小生成树 ##

##### Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ #####

## 题目描述 ##

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

## 输入 ##

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

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

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

## 输出 ##

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

## 示例输入 ##

3 2
    1 2 1
    1 3 1
    1 0

## 示例输出 ##

2
    0

## 提示 ##

## 来源 ##

赵利强

## 示例程序 ##

#include <stdio.h>  
    #include <string.h>  
    #define inf 2147483647  
    #define V 105  
    int vis[V],dis[V][V];  
    int lowc[V];  
        int prim(int cost[][V], int n)   
        {  
            int i, j, p;  
            int minc, res = 0;  
            memset(vis, 0, sizeof(vis));  
            vis[1] = 1;  
            for (i=1; i<=n; i++)  
            {  
                lowc[i] = cost[1][i];  
            }  
            for (i=1; i<n; i++)  
            {  
                minc = inf;  
                p = -1;  
                for (j=1; j<=n; j++)  
                {  
                    if (0 == vis[j] && minc > lowc[j])  
                    {  
                        minc = lowc[j];  
                        p = j;  
                    }  
                }  
                if (inf == minc)  
                {  
                    return -1;   
                }  
                res += minc;  
                vis[p] = 1;  
                for (j=1; j<=n; j++)  
                {  
                    if (0 == vis[j] && lowc[j] > cost[p][j])  
                    {  
                        lowc[j] = cost[p][j];  
                    }  
                }  
            }  
            return res;  
        }  
        int main()  
        {  
            int m,n,i,j,x,y,w;  
            while(scanf("%d%d",&n,&m)!=EOF)  
            {  
                for(i=1;i<=n;i++)  
                {  
                    for(j=1;j<=n;j++)  
                    {  
                        if(i==j)  
                        {  
                            dis[i][j]=0;  
                        }  
                        else  
                        {  
                            dis[i][j]=inf;  
                        }  
                    }  
                }  
                for(i=0;i<m;i++)  
                {  
                    scanf("%d%d",&x,&y);  
                    scanf("%d",&w);  
                   if(dis[x][y]>w)  
                    {  
                        dis[y][x]=w;  
                        dis[x][y]=w;  
                    }  
                }  
                printf("%d\n",prim(dis,n));  
            }  
        }