【灾后重建】蓝桥杯第六届省赛C/C++大学A组（并查集+Kruskal算法）

╰+攻爆jí腚メ 2022-11-26 09:44 100阅读 0赞

问题描述：  
  Pear市一共有N（<=50000）个居民点，居民点之间有M（<=200000）条双向道路相连。这些居民点两两之间都可以通过双向道路到达。这种情况一直持续到最近，一次严重的地震毁坏了全部M条道路。  
  震后，Pear打算修复其中一些道路，修理第i条道路需要Pi的时间。不过，Pear并不打算让全部的点连通，而是选择一些标号特殊的点让他们连通。  
  Pear有Q（<=50000）次询问，每次询问，他会选择所有编号在\[l,r\]之间，并且 编号 mod K = C 的点，修理一些路使得它们连通。由于所有道路的修理可以同时开工，所以完成修理的时间取决于花费时间最长的一条路，即涉及到的道路中Pi的最大值。  
  你能帮助Pear计算出每次询问时需要花费的最少时间么？这里询问是独立的，也就是上一个询问里的修理计划并没有付诸行动。

【输入格式】  
第一行三个正整数N、M、Q，含义如题面所述。  
接下来M行，每行三个正整数Xi、Yi、Pi，表示一条连接Xi和Yi的双向道路，修复需要Pi的时间。可能有自环，可能有重边。1<=Pi<=1000000。

接下来Q行，每行四个正整数Li、Ri、Ki、Ci，表示这次询问的点是\[Li,Ri\]区间中所有编号Mod Ki=Ci的点。保证参与询问的点至少有两个。

【输出格式】  
输出Q行，每行一个正整数表示对应询问的答案。

【样例输入】  
7 10 4  
1 3 10  
2 6 9  
4 1 5  
3 7 4  
3 6 9  
1 5 8  
2 7 4  
3 2 10  
1 7 6  
7 6 9  
1 7 1 0  
1 7 3 1  
2 5 1 0  
3 7 2 1

【样例输出】  
9  
6  
8  
8

【数据范围】  
对于20%的数据，N,M,Q<=30  
对于40%的数据，N,M,Q<=2000  
对于100%的数据，N<=50000,M<=2\*10^5,Q<=50000. Pi<=10^6. Li,Ri,Ki均在\[1,N\]范围内，Ci在\[0,对应询问的Ki)范围内。

资源约定：  
峰值内存消耗 < 256M  
CPU消耗 < 5000ms

**思路分析：** 看到CPU消耗最多竟然可以达到5秒，于是就想到最简单的一种解法，不过后来证明是超时了的。我们先来理一理题目：一共N个结点，M条边，每条边上都有权值，并且可能有环，**实际上就是一个可能有环的无向网**。现在每次询问，我都选择一部分结点（l到r且mod k为c的点），**假设这部分点有5个，那么我们要干的事情就是找到四条边使它们连通。**  
  如果每次询问都是所有点，那么其实就是**最小生成树**的生成，然后输出其中最大边的取值。但本题只是选择一部边来生成“最小生成树”。  
  最小生成树的生成算法比较有名的有Kruskal算法，本题也采用这个算法。Kruskal算法思想如下：一共N个点，我们需要选择N-1条边。

1.  先把所有边按照权值从小到大排序。
2.  依次选择每条边，判断该边的两个顶点是否在一个集合里面，是的话就跳过该边（加进去会出现环），继续选择下一条边。
3.  重复步骤2，直到选够N-1条边。

那么本题的思路也就十分明确了：我们按照Kruskal算法的思想，依次选择边，如果该边加进去之后能够使得我们想要连通的点全部连通，那么我们就输出该条边的权值。

那啥是并查集？怎么判断是不是在不在一个集合当中？可以参考一下这篇博文：[并查集的介绍及简单应用—蓝桥杯真题：合根植物][Link 1]  
  因此，写代码思路就很清晰了：

#include<bits/stdc++.h>
    using namespace std;
    
    int N, M, Q;
    const int maxM = 2e5;
    const int maxN = 5e4 + 5;
    int par[maxN];
    
    //定义边 
    struct edge { 
    	int begin, end, cost;
    }edges[maxM];
    
    bool cmp(edge x, edge y) { 
    	return x.cost<y.cost;
    }
    
    //并查集
    int get_root(int a) {     //求根节点 
    	if(par[a] != a) { 
    		par[a] = get_root(par[a]);
    	}
    	return par[a];
    }
    
    //查询是否在同一集合中 
    bool query(int a,int b) { 
         return get_root(a) == get_root(b);
    }
    
    //合并两个结点 
    void merge(int a,int b) { 
         par[get_root(a)] = get_root(b);
    }
    
    //每次询问都要初始化 
    void init() { 
    	for(int i = 1;i <= N;i++) { 
    		par[i] = i;
    	}
    }
    
    int solve(int l, int r, int k, int c) { 
    	init();
    	for(int i = 0;i < M;i++) { 
    		int begin = edges[i].begin;
    		int end = edges[i].end;
    		int cost = edges[i].cost;
    		
    		if(get_root(begin) == get_root(end)) {    //该边的两个结点已经在同一个集合中 
    			continue;
    		}else { 
    			merge(begin, end);  //合并加边 
    		}
    		//每添加一条边都要判断一下已经满足条件，是就退出 
    		bool flag = true;
    		int parent = 0;
    		//检查l到r中模k余c的点是否已经连通 
    		for(int i = l;i <= r;i++) { 
    			if(i % k == c) { 
    				if(parent == 0) { 
    					parent = get_root(i);
    				}else { 
    					if(parent != get_root(i)) {    //实际上就是检查这些结点是不是在同一个集合里 
    						flag = false;
    						break;
    					}
    				}
    			}
    		}
    		if(flag) { 
    			cout<<cost<<endl;  //已经在同一个集合，说明已经连通 
    			break;
    		}
    	}
    	return 1;
    }
    
    int main() { 
    	cin>>N>>M>>Q;
    	for(int i = 0;i < M;i++) { 
    		cin>>edges[i].begin>>edges[i].end>>edges[i].cost;
    	} 
    	sort(edges, edges + M, cmp);   //边从小到大排序 
    	for(int i = 0;i < Q;i++) { 
    		int l, r, k, c;
    		cin>>l>>r>>k>>c;
    		solve(l, r, k, c);
    	}
    	return 0;
    }

[Link 1]: https://blog.csdn.net/Cyril_KI/article/details/106054630