ABC250H 题解

题面

我们先考虑如何让连续的不在房子中的时间尽量短：

我们考虑两个有房子的点 \(x,y\)，如果 \(x\rightsquigarrow u\xrightarrow{w} v\rightsquigarrow y\) 这条路径上除了 \(x,y\) 不存在有房子的点，那么我们可以找到这样一条路径，一定不劣：

令 \(a,b\) 分别为最靠近 \(u,v\) 的有房子的点，那么存在 \(x\rightsquigarrow u\xrightarrow{w} v\rightsquigarrow b\rightsquigarrow v\xrightarrow{w} u\rightsquigarrow a\rightsquigarrow u\xrightarrow{w} v\rightsquigarrow y\) 这样一条路径，并且相邻两个有房子的点 \(x,b,a,y\) 之间路径长度显然小于 \(x\rightsquigarrow u\xrightarrow{w} v\rightsquigarrow y\)。

证明就是 \(dis(x,u)\ge dis(x,a),dis(y,v)\ge dis(b,v)\)，分别比较一下就行了。

注意这道题是查询某情况下 \(x\) 和 \(y\) 是否联通，可以考虑动态加边然后并查集维护。

然后我们考虑：一条 \(u\xrightarrow{w} v\) 的边什么时候应该被加入图中？

经过上面的贪心，我们可以大概猜到答案是当 \(t\geq dis(a,u)+w+dis(v,b)\) 时。

接下来说明这个结论是对的：

首先，一定不存在经过 \(u\xrightarrow{w} v\) 的路径，且 \(t<dis(a,u)+w+dis(v,b)\)，证明显然。

然后对于一条经过 \(u\xrightarrow{w} v\) 的路径，且这条边是耗时最长的，一定可以构造出 \(t=dis(a,u)+w+dis(v,b)\) 的答案：

设一条路径上的点为 \(x,u_1,u_2,\cdots,u_d,y\)，设 \(v_i\) 为离 \(u_i\) 最近的有房子的点，那么新路径 \(x,u_1,v_1,u_1,u_2,v_2,u_2,\cdots,u_{d-1},v_{d-1},u_{d-1},y\) 上的 \(t\) 就是各边的加入时间的最大值（\(\max_{i=1}^{d-1}(dis(v_i,u_i)+dis(u_i,u_{i+1})+dis(u_{i+1},v_{i+1}))\)）。

所以只要按照 \(dis(a,u)+w+dis(v,b)\) 排序，按询问的 \(t\) 逐次加入，并查集查询即可。

预处理到最近有房子的点的距离可以在 dijkstra 时把所有有房子的点先一起加入优先队列。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 2e5 + 5, M = 4e5 + 5;
int fst[N], nxt[M], to[M], w[M], h = 2;
void add(int x, int y, int z)
{
    nxt[h] = fst[x], fst[x] = h, to[h] = y, w[h] = z, h ++;
}

int fa[N];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
inline void merge(int x, int y) {fa[find(x)] = find(y);}

int n, m, k;
ll dis[N];
void dij()
{
    using pii = pair<ll, int>;
    priority_queue<pii, vector<pii>, greater<pii>> q;
    memset(dis, 0x3f, sizeof dis);
    bool vis[N] = {};
    for(int i = 1; i <= k; i ++)
    {
        dis[i] = 0;
        q.push({0, i});
    }
    while(q.size())
    {
        int t = q.top().second; q.pop();
        if(vis[t]) continue;
        vis[t] = 1;
        for(int ei = fst[t], i = to[ei], w = ::w[ei]; ei; ei = nxt[ei], i = to[ei], w = ::w[ei])
        {
            if(dis[i] <= dis[t] + w) continue;
            dis[i] = dis[t] + w;
            q.push({dis[i], i});
        }
    }
}

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i ++) fa[i] = i;
    for(int i = 1; i <= m; i ++)
    {
        int x, y, z; cin >> x >> y >> z;
        add(x, y, z);
        add(y, x, z);
    }
    dij();
    vector<pair<ll, int>> edge;
    for(int i = 2; i < h; i += 2)
        edge.push_back({dis[to[i]] + dis[to[i ^ 1]] + w[i], i});
    sort(edge.begin(), edge.end());
    auto it = edge.begin();
    int q; cin >> q;
    while(q --)
    {
        ll x, y, t;
        cin >> x >> y >> t;
        while(it != edge.end() && it->first <= t)
            merge(to[it->second], to[it->second ^ 1]), it ++;
        if(find(x) == find(y)) cout << "Yes\n";
        else cout << "No\n";
    }

    return 0;
}

扩展 CF1253F：从判定是否可行到变为求出 \(t\) 的最小值。

在这道题的基础上使用可撤销并查集加上整体二分即可解决。