我的思考——修复公路

· · 题解

我用的方法是并查集和生成最小树。

我打算详细地讲一讲。

并查集

并查集是对树的一种操作，旨在找到某个节点的公共祖先（最老公共祖先）。我们先讲一下并。

并

并就是讲两个节点合并到一个集合里面（这个集合必须是树），每个节点对应一个祖先，最老公共祖先的祖先就是自己，而每个节点在合并前的初始值也是自己，也就是：若有一个节点 a ，设它的祖先为 s[a] ，那么它的初始值就是 s[a]=a 。这个合并操作并不难，只要判断一下这两个节点是否有祖先，没有就很好办，直接随便连，比如： a 和 b ，他们都没有祖先（也就是祖先是自己），那么就可以 s[a]=b 了，如果 s[a] \neq a ，那么就让 b 的最老祖先（可能是自己）再往上多一个祖先 s[a] ，此时 b 的最老祖先也就是 a 的最老祖先了（不一定是 a ）。具体算法如下：

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 来找，再往上找，这样的话代码就是：

int findfather(int s[], int x) 
{
    if(x!=s[x])//如果不是最老祖先，那么就往上继续找
        x=findfather(s, s[x]);//从上面传过来的参数
    return s[x];//是祖先，就返回最老祖先的值
}

但是，这样做的话，会有很多重复工作。比如我刚才找 1 ，现在找 2 ，那么你就重复搜索了 2 。此时我们就需要压缩路径，以便后面查找时更便捷。压缩路径的话，就是在查找的时候，顺带把经过的节点的祖先直接指向最老祖先，那么后面找最老祖先的时候，就一步到位了。代码如下：

int findfather(int *s, int x)//*s代表的是直接对s进行操作 
{
    if(x!=s[x])//不是最老祖先
        s[x]=findfather(s, s[x]);//改变其指向，一直往上指，直到最老祖先。
    return s[x];//是最老祖先，返回最老祖先的值
}

这种方法十分巧妙，压缩路径之后，查找的速度也会快得多。

关于本题目

由于题目原本不是树，而是图，而题目又问的是最短修好路得时间，如果是图，那么会有多条路联通两个节点，而其中必定有一条最短时间修好的路，那么最终必定是其中的包含的最小树，所以我们要生成最小树。

最小生成树之Kruskal算法

这个算法用到的方法是，先将所有边按照权重（此处是时间长短）排序，我是从小到大排序的。排序用到的算法复杂度只能是 O(nlgn) 以下的，不然会超时。比如快速排序，这些必须学，此处不做赘述。排好序以后，就从权重最小的边开始，因为此时所有节点的祖先值都为自己（也就是所有的节点都是独立的），运用并查集进行查的操作，看一下边的左右节点的祖先是否相同，如果最老祖先相同，就代表这两个节点已经在一个树里面了，你再去连这两个节点，就会练成图，所以最老祖先相同则不连，如果有不同的最老祖先，那么就对这两个节点进行

并的操作，这样还是树。直到最后，这个算法完毕后，最小树就生成了。最小生成树具体算法如下：

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;
}

最后实现

#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;
}