7-10 公路村村通（30 分) 最小生成树

傷城~ 2022-02-27 14:16 196阅读 0赞

7-10 公路村村通 （30 分)

现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。

### 输入格式: ###

输入数据包括城镇数目正整数N（≤1000）和候选道路数目M（≤3N）；随后的M行对应M条道路，每行给出3个正整数，分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见，城镇从1到N编号。

### 输出格式: ###

输出村村通需要的最低成本。如果输入数据不足以保证畅通，则输出−1，表示需要建设更多公路。

### 输入样例: ###

6 15
    1 2 5
    1 3 3
    1 4 7
    1 5 4
    1 6 2
    2 3 4
    2 4 6
    2 5 2
    2 6 6
    3 4 6
    3 5 1
    3 6 1
    4 5 10
    4 6 8
    5 6 3

### 输出样例: ###

最小生成树 Kruskal。

#include<stdio.h>
    #include<string.h>
    #include<math.h>
    #include<iostream>
    #include<string>
    #include<sstream>
    #include<algorithm>
    #include<map>
    #include<set>
    #include<queue>
    #include<stack>
    #include<vector>
    using namespace std;
    #define inf 0x3f3f3f3f
    #define LL long long
    struct sb
    {
    	int u,v,w;
    }p[3005];
    
    int father[1005];
    bool cmp(sb a, sb b)  
    { 
    	return a.w<b.w;
    }  
    int find(int x)
    {
    	int r=x,i=x,j;
    	while(father[r]!=r)
    	r=father[r];
    	while(father[i]!=i)
    	{
    		j=father[i];
    		father[i]=r;
    		i=j;
    	}
    	return r;
    }
    void conbime(int x,int y)
    {
    	int xx=find(x);
    	int yy=find(y);
    	if(xx!=yy)
    	father[xx]=yy;
    }
    int main()
    {
    	int n,m,i,j,k,x,y,z;
    	scanf("%d%d",&n,&m);
    	for(i=0;i<m;i++)
    		scanf("%d%d%d",&p[i].u,&p[i].v,&p[i].w);
    	sort(p,p+m,cmp);
    	for(i=1;i<=n;i++)father[i]=i;
    	int cnt=0,ans=0;
    	for(i=0;i<m;i++)
    	{
    		if(find(p[i].u)!=find(p[i].v))
    		{
    			conbime(p[i].u,p[i].v);
    			cnt++;
    			ans+=p[i].w;
    		}
    	}	
    	if(cnt==n-1)
    	printf("%d\n",ans);
    	else
    	printf("-1\n");
    	return 0;
    }