Luogu 1111 修复公路（最小生成树）
Description
A地区在地震过后，连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。
给出A地区的村庄数N，和公路数M，公路是双向的。并告诉你每条公路的连着哪两个村庄，并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车，即最早什么时候任意两条村庄都存在至少一条修复完成的道路（可以由多条公路连成一条道路）
第1行两个正整数N，M
下面M行，每行3个正整数x, y, t，告诉你这条公路连着x,y两个村庄，在时间t时能修复完成这条公路。
Output
如果全部公路修复完毕仍然存在两个村庄无法通车，则输出-1，否则输出最早什么时候任意两个村庄能够通车。
4 4 1 2 6 1 3 4 1 4 5 4 2 3
Sample Output
5
Http
Luogu:https://www.luogu.org/problem/show?pid=1111
Source
最小生成树 并查集
题目大意
求图中满足所有点联通的边的集合中最大值最下（说得简单点，就是求一个图的最小生成树并输出树上的最大边）
解决思路
首先用克鲁斯卡尔算法求出最小生成树，具体做法是：
将所有的边按照边权值从小到大排序从第一条边开始枚举，每次判断这条边的两端点，若都已经在一个连通块里了，跳过，若不在，连接这条边并合并这两个连通块持续上述操作，直到连接了n-1条边（为什么是n-1条呢？因为一棵树的边就是n-1条啊）或是所有的边都扫描过了（此时代表无解，原图不连通）
那么现在的问题就是如何判断两个点已经在同一连通块中了呢？
没错！我们用并查集来判断连通块。
定义一个F[i]（代码中用Mayuri[i]）来表示i所属的并查集编号。开始时每一个点都是一个孤立的连通块，所以每一个F[i]=i。在合并两个点u,v时，只要将u,v所在的并查集合并就可以将两个连通块合并了，具体操作就是将F[u]置为F[v]，但这样是有问题的，因为u所在的并查集编号并不一定是F[u]，所以要一直向上搜寻，我们用一个Find()函数来表示，递归地找到最早的编号。
但是这样有可能出现树退化成链表的情况，所以在Find函数查找时，顺便压缩路径（具体请看代码）
代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
class Road
{
public:
int u,v,w;
};
bool operator < (Road a,Road b)//因为要排序，所以重载一下小于运算符
{
return a.w<b.w;
}
const int maxN=2000;
const int maxM=101000;
const int inf=2147483647;
int n,m;
int Mayuri[maxN];
Road E[maxM];
int Find(int x);
int main()
{
int Ans=0;
int cnt=0;
cin>>n>>m;
for (int i=1;i<=m;i++)
{
cin>>E[i].u>>E[i].v>>E[i].w;
}
sort(&E[1],&E[m+1]);
for (int i=1;i<=n;i++)//并查集初始化
Mayuri[i]=i;
int i=0;
do
{
i++;
int fu=Find(E[i].u);
int fv=Find(E[i].v);
if (fu!=fv)//如果u,v不在同一个连通块，就合并
{
cnt++;//统计选择了的边的个数，便于及时退出和判断是否有解
Ans=max(E[i].w,Ans);//更新答案
Mayuri[fu]=fv;
}
if (cnt==n-1)//当已经形成一个树时，及时退出循环
break;
}
while (i<m);
if (cnt==n-1)
cout<<Ans<<endl;
else
cout<<-1<<endl;
return 0;
}
int Find(int x)
{
if (Mayuri[x]!=x)
Mayuri[x]=Find(Mayuri[x]);//压缩路径，让每一个点都直接指向其并查集编号的那个点
return Mayuri[x];
}
转载于:https://www.cnblogs.com/SYCstudio/p/7137378.html
相关资源：苏少版音乐一上《京剧锣鼓》课件
