只有10分!救命!
  • 板块P1111 修复公路
  • 楼主XDST
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/10/8 20:38
  • 上次更新2023/10/27 08:09:26
查看原帖
只有10分!救命!
722952
XDST楼主2022/10/8 20:38
#include<iostream>
#include<algorithm>
#include<cstdio>
#define max_road_count 100000
#define max_village_count 1000

long long village_count;
long long road_count;
long long point_father[max_village_count];
long long ans_time_cost;
struct road
{
	long long village_one;
	long long village_two;
	long long time_cost;
}roads[max_road_count];

//输入函数 
void input_data()
{
	long long village_list_i;
	scanf("%lld%lld",&village_count,&road_count);
	for(long long i=0;i<road_count;i++)
		scanf("%lld%lld%lld",&roads[i].village_one,&roads[i].village_two,&roads[i].time_cost);
}

//并查集初始化 
void init_forest()
{
	for(long long i=0;i<village_count;i++)
		point_father[i]=i;
}

//sort比较规则 
bool cmp(road a,road b)
{
	return a.time_cost<b.time_cost;
}

//找节点的根节点 
long long find_root(long long one_point)
{
	if(point_father[one_point]==one_point)
		return one_point;
	return point_father[one_point]=find_root(point_father[one_point]);
}

//合并两个元素所在集合 
void merge(long long point_a,long long point_b)
{
	long long root_a=find_root(point_a);
	long long root_b=find_root(point_b);
	point_father[point_a]=root_b;
}

//判断两个函数是否在同一个集合 
bool judge(long long point_a,long long point_b)
{
	if(find_root(point_a)==find_root(point_b))
		return 1;
	return 0;
}

//最小生成树 
void creact()
{
	for(int i=0;i<road_count;i++)
	{
		if(!judge(roads[i].village_one,roads[i].village_two))
		{
			merge(roads[i].village_one,roads[i].village_two);
			if(roads[i].time_cost>ans_time_cost)
				ans_time_cost=roads[i].time_cost;
		}
	}
}

int main()
{
	input_data();
	init_forest();
	std::sort(roads,roads+road_count,cmp);
	creact();
	printf("%lld",ans_time_cost);
	
	return 0;
}
2022/10/8 20:38
加载中...