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

悠悠 2022-09-25 07:22 112阅读 0赞

## 题目描述 ##

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

## 输入 ##

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

## 输出 ##

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

## 示例输入 ##

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

## 示例输出 ##

## 提示 ##

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    int INF=100000;//INF代表村庄之间不连接
    int edge[1001][1001],lowc[10001],vis[10001];//lowc数组存储候选边
    int prim(int n)
    {
        int i,j,p;
    	int min,sum=0;
    	
    	//标记0村庄已访问
    	vis[0]=1;
    
    	//存储0村庄和其他村庄之间的权值作为候选边
    	for(i=1;i<n;i++)
    		lowc[i]=edge[0][i];
    
    	//访问其他n-1个村庄
    	for(i=1;i<n;i++)
    	{
            min=INF;
    		p=-1;
    
    		//挑出权值最小的路
    		for(j=0;j<n;j++)
    		{
    			if(vis[j]==0&&min>lowc[j])
    			{
    				min=lowc[j];
                    p=j;
    			}
    		}
    
    		if(INF==min)
    			return -1;
    		sum=sum+min;
    	    vis[p]=1;
    
    		//修改候选边数组
    	    for(j=0;j<n;j++)
    		{
    		    if(vis[j]==0&&lowc[j]>edge[p][j])
    			    lowc[j]=edge[p][j];
    		}
    	}
    	return sum;
    }
    int main()
    {
    	int n,e,i,j,x,y,w;
    	while(scanf("%d%d",&n,&e)!=EOF)
    	{
    		//初始化
    		memset(vis,0,sizeof(vis));
    		for(i=0;i<n;i++)
    		{
    			for(j=0;j<n;j++)
    			{
    				if(i==j)
                        edge[i][j]=0;
    				else
    					edge[i][j]=INF;
    			}
    		}
    
    		//连接村庄及赋予权值
    		for(i=0;i<e;i++)
    		{
    			scanf("%d%d%d",&x,&y,&w);
    			if(edge[x-1][y-1]>w)
    			{
    				edge[x-1][y-1]=w;
    				edge[y-1][x-1]=w;
    			}
    		}
    
    		//普里姆算法
    		printf("%d\n",prim(n));
    	}
    	return 0;
    }