自动搬运

查看原文

来自洛谷，原作者为

	望月Asta 语言的难产->语言的便秘

搬运于2025-08-24 22:34:58，当前版本为作者最后更新于2021-12-25 21:24:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

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

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

解法

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

• $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;
}