Dijkstra 求“传递闭包”

· · 个人记录

第一篇题解，Dijkstra求连通性

看了下数据范围 1\le n\le 1000，边的个数 m 的范围在 m\le 1e6 的样子，并查集显然是可以的。 但是我突然想到了用 \mathcal{Floyd} 求传递闭包的算法。遂得到如下解法：

0x0 虚拟结点（dummy node）

显然，上下两个平面都可以视为一个虚拟结点，对于这两个虚拟节点 s,t我们特殊判断其他空洞是否与其相交（方法很简单，特殊判断 z 即可）

所以我们共有 n + 2 个结点，其中s\rightarrow 0，t\rightarrow n+1 其余的点在区间[1, n]内。

0x1 建图&&\mathcal{Dijkstra}

那么我们判断s,t之间的连通性实际上不就是判断他们之间是否存在距离嘛（不管大还是小，只要有距离就可以了）。

那，仿照Dijkstra 算法，我们只需要修改转移函数即可。

这样之后就可以直接跑 Dijkstra 快到起飞！

#include <bits/stdc++.h>
#define vt std::vector
#define int long long
constexpr int inf = 0x3f3f3f3f;
int d[1005][1005]; // 代表两点之间的关系
int g[1005]; // 代表从开始结点 s 出发到其他点的关系
// 用 tup 代替结构体
using tup = std::tuple<long long, long long, long long>;

int n, h, r;

void dijkstra(int s){
    for (int i = 0; i <= n + 1; ++ i) g[i] = (i == 0 ? 1 : 0);
    vt<int> vis(n + 2, 0);
    for (int i = 0; i < n + 2; ++ i){
        int x;
        for (int y = 0; y <= n + 1; ++ y) if (!vis[y] && g[y]) x = y;
        vis[x] = 1;
        for (int y = 0; y <= n + 1; ++ y) g[y] |= (g[x] & d[x][y]); // 关键一步
    }
}

void solve(){
    std::cin >> n >> h >> r;
    vt<tup> points;
    for (int i = 0; i < n; ++ i){
        int x, y, z;
        std::cin >> x >> y >> z;
        points.push_back(std::make_tuple(x, y, z));
    }

    auto calc = [&](tup &a, tup &b){
        int dis = 
            (std::get<0>(a) - std::get<0>(b)) * (std::get<0>(a) - std::get<0>(b)) +
            (std::get<1>(a) - std::get<1>(b)) * (std::get<1>(a) - std::get<1>(b)) +
            (std::get<2>(a) - std::get<2>(b)) * (std::get<2>(a) - std::get<2>(b));
        if (dis <= (4 * r * r)) return 1;
        return 0;
    };

    int s = 0, t = n + 1;
    memset(d, 0, sizeof(d));
    for (int i = 1; i <= n; ++ i){
        for (int j = i; j <= n; ++ j){
            if (i == j) d[i][j] = 0;
            d[i][j] = d[j][i] = calc(points[i - 1], points[j - 1]);
        }
        if (std::get<2>(points[i - 1]) <= r) d[0][i] = d[i][0] = 1;
        if (h - std::get<2>(points[i - 1]) <= r) d[i][n + 1] = d[n + 1][i] = 1;
    }
    dijkstra(s);
    std::cout << (g[t] ? "Yes" : "No") << "\n";
}

signed main(){
    std::ios::sync_with_stdio(0), std::cin.tie(0);
    int t;
    std::cin >> t;
    while (t--) solve();
    return 0;
}