P7991 题解

望月Asta · 2021-12-25 21:24:39 · 题解

题意

给出一个 n 个点 m 条边，编号从 1 到 n 的无向图，可以以 (i - j)^2 的代价在任意的 i,j 之间连一条边。

现在可以进行不超过两次连边操作，求使得 1 和 n 两点连通的最小代价。

解法

首先不超过两次连边一定是以下几种形式中的一种 :

• 从 1 和 n 分别所在的连通分量中找出差值最小的两个点连边，共连一条边。

• 将 1 和 n 分别所在的连通分量和第三个连通分量相连，共连两条边。

可以发现都是把某个点所在的连通分量与 1 或 n 连通的过程。

令 f_i 表示将点 i 所在的连通分量与 1 连接的最小代价，g_i 表示将点 i 所在的连通分量与 n 连接的最小代价。

那么答案为 : \min_{i = 1}^{n} \{f_i + g_i\}。

然后考虑如何求出 f 和 g。

首先可以求出初始与 1,n 在同一连通分量的点的集合，记为 F 与 G。

对于一个点 u，在 F,G 中分别二分查找得到与其差值最小的点并尝试更新最小值。

时间复杂度 \mathcal{O} (n \log n)。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>

typedef long long ll;
constexpr int N = 100005;

ll f[N],g[N];
int F[N],G[N],fa[N];

int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

void solve() {
    int n,m;
    scanf("%d %d",&n,&m);
    memset(f,127,sizeof(f));
    memset(g,127,sizeof(g));
    for(int i = 1;i <= n;++i)
        fa[i] = i;
    for(int i = 1;i <= m;++i) {
        int u,v;
        scanf("%d %d",&u,&v);
        u = find(u),v = find(v);
        if(u == v) continue;
        fa[u] = v;
    }
    int r1 = find(1),rn = find(n);
    f[r1] = 0,g[rn] = 0;
    int cntF = 0,cntG = 0;
    for(int i = 1;i <= n;++i) {
        int u = find(i);
        if(u == r1) F[++cntF] = i;
        else if(u == rn) G[++cntG] = i;
    }
    for(int i = 1;i <= n;++i) {
        int u = find(i);
        if(u != r1) {
            int pre = std::upper_bound(F + 1,F + cntF + 1,i) - F - 1;
            f[u] = std::min(f[u],(ll)(i - F[pre]) * (i - F[pre]));
            if(pre < cntF) {
                ++pre;
                f[u] = std::min(f[u],(ll)(i - F[pre]) * (i - F[pre]));
            }
        }
        if(u != rn) {
            int nxt = std::upper_bound(G + 1,G + cntG + 1,i) - G;
            g[u] = std::min(g[u],(ll)(i - G[nxt]) * (i - G[nxt]));
            if(nxt > 1) {
                --nxt;
                g[u] = std::min(g[u],(ll)(i - G[nxt]) * (i - G[nxt]));
            }
        }
    }
    ll ans = (ll)(n - 1ll) * (n - 1ll);
    for(int i = 1;i <= n;++i) {
        int u = find(i);
        ans = std::min(ans,f[u] + g[u]);
    }
    printf("%lld\n",ans);
}

int main() {
    int T;
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}