我的思考——修复公路

我用的方法是**并查集和生成最小树**。 我打算详细地讲一讲。 ##并查集 并查集是对树的一种操作，旨在找到某个节点的公共祖先（最老公共祖先）。我们先讲一下并。 ###并 并就是讲两个节点合并到一个集合里面（这个集合必须是树），每个节点对应一个祖先，最老公共祖先的祖先就是自己，而每个节点在合并前的初始值也是自己，也就是：若有一个节点$ 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 } ``` ###查 有时候我们需要查某个节点的最老祖先是谁，主要是为了下面判断某两个节点的最老祖先是否相同而准备的。假如有这样一组关系：  比如我们要找$ 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; } ```