pat 数据结构与算法题目集

题目描述

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

输入格式:

输入数据包括城镇数目正整数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

输出样例:

12

ac代码

/*
    Name:
    Copyright:
    Author:  流照君
    Date: data
    Description:
*/
#include <iostream>
#include<string>
#include <algorithm>
#include <vector>
#define inf 105
using namespace std;
typedef long long ll;
int mat[inf],n,m; 
typedef struct node{
	int v1,v2,e;
	 node(int x,int y,int z)
	 {
	 	v1=x;
	 	v2=y;
	 	e=z;
	 }
}edge;
edge arr[inf];
bool cmp(edge e1,edge e2)
{
	if(e1.e<e2.e)
	return true;   
}
int find(int x)
{
	if(mat[x]!=x)
	return mat[x]=find(mat[x]);  //路径压缩 
	else 
	return x;
}
int merge(int x,int y)   //并查集 
{
	int x1=find(x);
	int y1=find(y);
	if(x1!=y1)
	{
		mat[y1]=x1;
		return 1;
	}
	else
	return 0; 
}
int main(int argc, char** argv)
{
#ifdef ONLINE_JUDGE//条件编译，如果有oj则忽略文件读取
#else
	//freopen("in.txt", "r", stdin);//输入输出文件重定向
	//freopen("out.txt", "w", stdout);
#endif  //#if, #ifdef, #ifndef这些条件命令的结束标志.
//代码位置
	int x,y,z,temp=1,cnt=0,sum=0;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	mat[i]=i;
	while(m--)
	{
		cin>>x>>y>>z;
		//arr[temp++].node(x,y,z);
		merge(x,y);
	}
	for(int i=1;i<=n;i++)
	{
		if(mat[i]==i)
		cnt++;
	}
	if(cnt!=1)
	{
		cout<<"-1"<<endl;
		return 0;
	}
	sort(arr+1,arr+m,cmp);
	cnt=0;
	for(int i=1;i<=n;i++)
	mat[i]=i;
	for(int i=1;i<=m;i++)
	{
		  if(merge(arr[i].v1,arr[i].v2))
		  {
		  	cnt++;
		  	sum=sum+arr[i].e;
		  }
		  if(cnt==(n-1))
		  break; 
	}
	cout<<sum<<endl;
    return 0;
}

最小生成树的两个算法都要用到并查集这数据结构，还判断新加的边的两个顶点是否在同一个集合里。
还有一件事，就是最小生成树两种算法其核心思想就是贪心