P1111 修复公路 题解

· · 题解

闲话

本题不难，写了 15 分钟就过了。

思路

题解区里好多都是并查集、最小生成树、kruskal 等优秀算法。蒟蒻不才，只会二分和图遍历。

那该怎么办呢？

如何二分

设答案在 (l,r) 的范围内，那么存在一个分界线 mid = (l + r) \div 2，如果 mid 答案成立，答案范围缩小至 (l,mid)，否则如果 mid 答案不成立，答案范围缩小至 (mid,r)。最后的答案为 r。

判断函数

judge 函数就是一个 dfs，访问到一个村庄，计数器加 1，如果 dfs 结束后计数器为 n，那么说明所有的村庄都遍历到了，否则不是。

判断是否无解

如果最晚修好的一条路修好后遍历到的村庄数不为 n，那么说明无解，输出 -1。

图的遍历

不用我多说了吧，就是一个模板，直接套就行了。

时间复杂度

dfs时间复杂度为 O(n + m)，调用了 \log n 次，所以总时间复杂度为 O(\log n(n + m))。

代码

#include <bits/stdc++.h>
using namespace std;
int n,m,cnt = 0,maxtime = 0;//n为村庄数，m为道路数，cnt为访问到的村庄数，maxtime为最晚修好的一条路修好的时间
bool vis[1001];//vis为是否访问过
vector <pair <int,int> > v[1001];//邻接表存图，pair的第一个元素指这个点连着的村庄，第二个元素指这条路修好的时间
void dfs(int x,int t){//模板
    vis[x] = true;//标记为已走过
    cnt++;//计数器加一
    for (auto y : v[x]) if (!vis[y.first] && t >= y.second) dfs(y.first,t);//枚举道路
    return;
}
int main(){
    scanf("%d%d",&n,&m);
    for (int i = 1; i <= m; i++) {
        int x,y,t;
        scanf("%d%d%d",&x,&y,&t);
        v[x].push_back({y,t});
        v[y].push_back({x,t});//存图
        maxtime = max(maxtime,t);//更新时间最大值
    }
    int l = 0,r = maxtime + 1,mid;
    while (l + 1 < r) {//二分
        memset(vis,false,sizeof(vis));
        cnt = 0;
        //多测不清空，爆零两行泪
        mid = (l + r) / 2;
        dfs(1,mid);
        if (cnt == n) r = mid;//答案可行，右边界左移
        else l = mid;//答案不可行，左边界右移
    }
    if (r == maxtime + 1) printf("-1");//不合法输出-1
    else printf("%d",r);//否则输出答案
    return 0;
}