基础算法题——修复公路（并查集、kruskal）

青旅半醒 2023-02-27 10:34 25阅读 0赞

[测试平台][Link 1]  
题目背景  
A地区在地震过后，连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。

题目描述  
给出A地区的村庄数N，和公路数M，公路是双向的。并告诉你每条公路的连着哪两个村庄，并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车，即最早什么时候任意两条村庄都存在至少一条修复完成的道路（可以由多条公路连成一条道路）

输入格式  
第1行两个正整数N,M

下面M行，每行 3 个正整数x, y, t，告诉你这条公路连着x,y两个村庄，在时间t时能修复完成这条公路。

输出格式  
如果全部公路修复完毕仍然存在两个村庄无法通车，则输出−1，否则输出最早什么时候任意两个村庄能够通车。

输入输出样例  
输入  
4 4  
1 2 6  
1 3 4  
1 4 5  
4 2 3  
输出  
5  
说明/提示  
N ≤ 1000, M ≤ 100000  
x ≤ N, y ≤ N, t ≤ 100000

--------------------

##### 注意点： #####

①、公路同时进行修复  
②、村庄之间是否连通  
③、最早实现村庄之间连通的时间

--------------------

##### 解题步骤： #####

###### 一、最早实现村庄之间连通的时间 ######

利用最小生成树的思路（ kruskal 算法），从修复公路时间最短开始遍历添加到连接的村庄集合中。

①、利用结构体 node 存储数据

struct node{ 
    	int a, b, c;
    }data[100010];

②、将结构数组 data 按照修复 a 与 b 之间公路的时间从小到大排序

bool cmp(node a, node b){ 
    	if(a.c<b.c) return true;
    	return false;
    }

--------------------

###### 二、判断村庄之间是否全部连通 ######

**暴力方法**  
每添加一条公路，利用并查集判断一次村庄之间是否连通，很显然这样很容易超时。

**优化方法**  
1、初始化  
①、利用并查集的思路，一个集合仅有一个“代表”，u\[i\]=i。  
②、count\_ 数组存储每个集合当前已连接村庄数量，例如 count\_ \[a\]：包含 a 村庄的集合数量。  
（每个都是单独的集合）

for(int i=1; i<=N; i++){ 
    	u[i]=i;
    	count_[i]=1;
    }

2、算法设计  
①、只需关注一个集合的“代表”已连接村庄数量是否为总村庄的数量。若两个集合连通则将变成一个集合，这个集合的“代表”已连接村庄数量等于先前两个集合“代表”已连接村庄数量之和。  
②、当出现集合的“代表”已连接村庄数量为总村庄的数量时，输出当前元素的修复公路时间。  
③、始终未出现集合的“代表”已连接村庄数量为总村庄的数量时，输出 -1。

//压缩路径
    int Find(int ab){ 
    	int t = ab;
    	while(u[ab] != ab){ 
    		ab = u[ab];
    	}
    	while(t != ab){ 
    		int z = t;
    		t = u[t];
    		u[z] = ab;
    	}
    	return ab;
    }
    
    for(int i=1; i<=M; i++){ 
    	int x = Find(data[i].a);
    	int y = Find(data[i].b);
    	if(x!=y){ 
    		u[y] = x;
    		count_[x] += count_[y];
    	}
    	if(count_[x] >= N){ 
    		cout<<data[i].c;
    		return 0;
    	}
    }

--------------------

整合代码

#include<bits/stdc++.h>
    using namespace std;
    int u[1010],count_[1010];
    
    struct node{ 
    	int a, b, c;
    }data[100010];
    
    bool cmp(node a, node b){ 
    	if(a.c<b.c) return true;
    	return false;
    }
    
    int Find(int ab){ 
    	int t = ab;
    	while(u[ab] != ab){ 
    		ab = u[ab];
    	}
    	while(t != ab){ 
    		int z = t;
    		t = u[t];
    		u[z] = ab;
    	}
    	return ab;
    }
    
    int main(){ 
    	int N, M;
    	cin>>N>>M;
    	
    	for(int i=1; i<=N; i++){ 
    		u[i]=i;
    		count_[i]=1;
    	}
    	
    	for(int i=1; i<=M; i++){ 
    		cin>>data[i].a>>data[i].b>>data[i].c;	//a为首领 
    	}
    	
    	sort(data+1, data+M+1, cmp);
    	for(int i=1; i<=M; i++){ 
    		int x = Find(data[i].a);
    		int y = Find(data[i].b);
    		if(x!=y){ 
    			u[y] = x;
    			count_[x] += count_[y];
    		}
    		if(count_[x] >= N){ 
    			cout<<data[i].c;
    			return 0;
    		}
    	}
    	cout<<"-1";
    	return 0;
    }

如果文章对你有帮助，请给我个赞吧：)

[Link 1]: https://www.luogu.com.cn/problem/P1111