我的思考——修复公路
Euler_Pursuer
2017-11-10 10:19:31
我用的方法是**并查集和生成最小树**。
我打算详细地讲一讲。
##并查集
并查集是对树的一种操作,旨在找到某个节点的公共祖先(最老公共祖先)。我们先讲一下并。
###并
并就是讲两个节点合并到一个集合里面(这个集合必须是树),每个节点对应一个祖先,最老公共祖先的祖先就是自己,而每个节点在合并前的初始值也是自己,也就是:若有一个节点$ a $,设它的祖先为$ s[a] $,那么它的初始值就是$ s[a]=a $。这个合并操作并不难,只要判断一下这两个节点是否有祖先,没有就很好办,直接随便连,比如:$ a $和$ b $,他们都没有祖先(也就是祖先是自己),那么就可以$ s[a]=b $了,如果$ s[a] \neq a $,那么就让$ b $的最老祖先(可能是自己)再往上多一个祖先$ s[a] $,此时$ b $的最老祖先也就是$ a $的最老祖先了(不一定是$ a $)。具体算法如下:
```cpp
void together(int *b, int a, int *s)//为了映照上面的说明,a和b就这样弄吧
{
if(s[*b]==*b)//a没有祖先时
s[*b]=a;//令a为b的父亲
else
together(&s[*b], a, s);//否则继续找b的祖先,直到b的最老祖先,然后将b的最老祖先的父亲设为a
}
```
###查
有时候我们需要查某个节点的最老祖先是谁,主要是为了下面判断某两个节点的最老祖先是否相同而准备的。假如有这样一组关系:
![](https://cdn.luogu.com.cn/upload/pic/10787.png)
比如我们要找$ 1 $的最老祖先,那么怎么找呢?那么就要通过$ 3 $来找,再往上找,这样的话代码就是:
```cpp
int findfather(int s[], int x)
{
if(x!=s[x])//如果不是最老祖先,那么就往上继续找
x=findfather(s, s[x]);//从上面传过来的参数
return s[x];//是祖先,就返回最老祖先的值
}
```
但是,这样做的话,会有很多重复工作。比如我刚才找$ 1 $,现在找$ 2 $,那么你就重复搜索了$ 2 $。此时我们就需要**压缩路径**,以便后面查找时更便捷。压缩路径的话,就是在查找的时候,顺带把经过的节点的祖先直接指向最老祖先,那么后面找最老祖先的时候,就一步到位了。代码如下:
```cpp
int findfather(int *s, int x)//*s代表的是直接对s进行操作
{
if(x!=s[x])//不是最老祖先
s[x]=findfather(s, s[x]);//改变其指向,一直往上指,直到最老祖先。
return s[x];//是最老祖先,返回最老祖先的值
}
```
这种方法十分巧妙,压缩路径之后,查找的速度也会快得多。
##关于本题目
由于题目原本不是树,而是图,而题目又问的是最短修好路得时间,如果是图,那么会有多条路联通两个节点,而其中必定有一条最短时间修好的路,那么最终必定是其中的包含的最小树,所以我们要生成最小树。
##最小生成树之Kruskal算法
这个算法用到的方法是,先将所有边按照权重(此处是时间长短)排序,我是从小到大排序的。排序用到的算法复杂度只能是$ O(nlgn) $以下的,不然会超时。比如快速排序,这些必须学,此处不做赘述。排好序以后,就从权重最小的边开始,因为此时所有节点的祖先值都为自己(也就是所有的节点都是独立的),运用并查集进行**查**的操作,看一下边的左右节点的祖先是否相同,如果最老祖先相同,就代表这两个节点已经在一个树里面了,你再去连这两个节点,就会练成图,所以最老祖先相同则不连,如果有不同的最老祖先,那么就对这两个节点进行
**并**的操作,这样还是树。直到最后,这个算法完毕后,最小树就生成了。最小生成树具体算法如下:
```cpp
int TREE(E *e, int *s)//直接对图和祖先值进行操作
{
int i, total=0;
SORT(e, 1, M);//对边进行权重大小排序
for(i=1;i<=M;i++)
if(findfather(s, s[e[i].a])!=findfather(s, s[e[i].b]))//是否有相同最老祖先
{
together(&s[e[i].a], s[e[i].b], s);//并操作
total++;//计算节点,为后面查看是否每个村庄都能连通做准备
ans=e[i].t;//我将ans定义为了全局变量,表示最小树中的最大通路时间
}
return total;
}
```
##最后实现
```cpp
#include <iostream>
using namespace std;
int N, M, ans;//全局变量,函数也可以直接用,无需传参数
struct E//图的边
{
int a;
int b;//俩顶点
int t;//修复时间
};
//中间忽略一堆函数,上面写了这里就不写了
int main()
{
int i, j, a, b, c;
int s[100010];
E e[100010];
cin>>N>>M;
for(i=1;i<=N;i++)
s[i]=i;
for(i=1;i<=M;i++)
cin>>e[i].a>>e[i].b>>e[i].t;
c=TREE(e, s);//生成最小树,并返回枝干数
if(c!=N-1)//如果没有将所有村庄连接起来(N个节点的树的枝干数目必须是N-1)
ans=-1;//则答案为不可能
cout<<ans;//否则输出生成最小树时处理好的答案
return 0;
}
```