思路错了就换一个呗

懵逼的 题目

BZOJ

扯淡的 题解

显然是找瓶颈路 要搞最小生成树

但是我们不可能给所有点连边…那么怎么找最小生成树呢…

一开始想的是从一个点开始bfs, 然后遇到城市就向上一个城市连边 并且更新”上一个城市”

后来发现一个格子要被更新多次, 复杂度有点爆炸

gayge表示我太菜了, 然后告诉我要从所有的点开始同时bfs, 两个城市相遇了就加边, 然后kruskal一波…

Orz

沙茶的 代码

被卡常了…懒得改了…

一直都是多了$0.6s$的样子

#pragma GCC optimize(2)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
#define mkp(a, b) make_pair(a, b)
#define DD double
#define pii pair<int, int>
#define rint register int 
#define MAXN (4000000 + 5)
#define MAXC (200000 + 5)
#define MAXL (20)
#define INF (0x7ffffff)
using namespace std;
const int xy[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
struct edg
{
    int from, to, cost, next;
    edg() {}
    edg(int f, int t, int c): from(f), to(t), cost(c) {}
} b[MAXC << 1];
int g[MAXC], cntb, n, h, w, vis[MAXN], col[MAXN], city[MAXC], fa[MAXC], size[MAXN], dis[MAXN];
int d[MAXC][MAXL], maxc[MAXC][MAXL], lgn, deep[MAXC], nc;
vector<edg> rb[MAXN];
inline int pti(const pii x)
{ return (x.first - 1) * w + x.second; }
inline pii itp(const int x)
{ return mkp(ceil((DD)x / w), x - ceil((DD)x / w) * w + w); }
inline int max(const int x, const int y)
{ return x > y ? x : y; }
inline int min(const int x, const int y)
{ return x < y ? x : y; }
inline void adn(const int from, const int to, const int cost)
{
    b[++cntb].next = g[from];
    b[cntb].from = from, b[cntb].to = to, b[cntb].cost = cost;
    g[from] = cntb;
}
inline bool pd(const pii x)
{ return (x.first <= h && x.first >= 1 && x.second <= w && x.second >= 1 && vis[pti(x)] >= 0); }
inline void init(const int s, const int c)
{
    queue<int> q;
    q.push(s);
    col[s] = c;
    while (!q.empty())
    {
        const int dq = q.front();
        q.pop();
        if (vis[dq] > 0)
            ++size[c];
        for (rint i = 0; i < 4; i++)
        {
            pii ndq = itp(dq);
            ndq.first += xy[i][0], ndq.second += xy[i][1];
            if (!pd(ndq))
                continue;
            if (!col[pti(ndq)])
                col[pti(ndq)] = c, q.push(pti(ndq));
        }
    }
}
void bfs()
{
    queue<int> q;
    for (rint i = 1; i <= n; i++)
        q.push(city[i]);
    while (!q.empty())
    {
        int dq = q.front();
        q.pop();
        for (rint i = 0; i < 4; i++)
        {
            pii ndq = itp(dq);
            ndq.first += xy[i][0], ndq.second += xy[i][1];
            int idq = pti(ndq);
            if (!pd(ndq) || vis[idq] == vis[dq])
                continue;
            if (vis[idq])
                rb[col[dq]].push_back(edg(vis[dq], vis[idq], dis[idq] + dis[dq]));
            else
            {
                vis[idq] = vis[dq];
                dis[idq] = dis[dq] + 1;
                q.push(idq);
            }
        }
    }
}
int find(const int x)
{ return (x == fa[x] ? x : (fa[x] = find(fa[x]))); }
void uni(const int x, const int y)
{ fa[find(x)] = find(y); }
inline bool cmp(const edg x, const edg y)
{ return x.cost < y.cost; }
void kruskal(const int dqc)
{
    sort(rb[dqc].begin(), rb[dqc].end(), cmp);
    int cnt = 0;
    for (rint i = 0, u, v; i < rb[dqc].size(); i++)
        if (find(u = rb[dqc][i].from) != find(v = rb[dqc][i].to))
        {
            uni(u, v);
            adn(u, v, rb[dqc][i].cost);
            adn(v, u, rb[dqc][i].cost);
            ++cnt;
            if (cnt == size[dqc] - 1)
                break;
        }
}
void dfs(int dq)
{
    for (rint i = 1; i <= lgn; i++)
    {
        d[dq][i] = d[d[dq][i - 1]][i - 1];
        maxc[dq][i] = max(maxc[dq][i - 1], maxc[d[dq][i - 1]][i - 1]);
    }
    for (rint i = g[dq]; i; i = b[i].next)
        if (d[dq][0] != b[i].to)
        {
            d[b[i].to][0] = dq;
            maxc[b[i].to][0] = b[i].cost;
            deep[b[i].to] = deep[dq] + 1;
            dfs(b[i].to);
        }
}
int solve(int x, int y)
{
    int re = 0;
    if (deep[y] > deep[x])
        swap(x, y);
    for (rint i = lgn; i >= 0; i--)
        if (deep[d[x][i]] >= deep[y])
            re = max(re, maxc[x][i]), x = d[x][i];
    if (x == y)
        return re;
    for (rint i = lgn; i >= 0; i--)
        if (d[x][i] != d[y][i])
            re = max(re, max(maxc[x][i], maxc[y][i])), x = d[x][i], y = d[y][i];
    return max(re, max(maxc[x][0], maxc[y][0]));
}
int lg(int x)
{
    int re = 0;
    while ((1 << re) < x)
        ++re;
    return re;
}
int main()
{
    int q;
    scanf("%d%d%d%d", &h, &w, &n, &q);
    lgn = lg(n);
    for (rint i = 1; i <= h; i++)
        for (rint j = 1; j <= w; j++)
        {
            char x = 0;
            while (x != '.' && x != '#')
                scanf("%c", &x);
            if (x == '.')    vis[pti(mkp(i, j))] = 0;
            else vis[pti(mkp(i, j))] = -1;
        }
    for (rint i = 1, srx, sry; i <= n; i++)
        scanf("%d%d", &srx, &sry), vis[city[i] = pti(mkp(srx, sry))] = i; 
    for (rint i = 1; i <= n; i++)
        if (!col[city[i]])
            init(city[i], ++nc);
    bfs();
    for (rint i = 1; i <= n; i++)    fa[i] = i;
    for (rint i = 1; i <= nc; i++)
        kruskal(i);
    for (rint i = 1; i <= n; i++)
        if (!d[i][0])
            d[i][0] = i, deep[i] = 1, dfs(i);
    for (rint i = 1, srx, sry; i <= q; i++)
    {
        scanf("%d%d", &srx, &sry);
        if (col[city[srx]] != col[city[sry]])
            puts("-1");
        else
            printf("%d\n", solve(srx, sry));
    }
    return 0;
}

By 沙茶 Cansult