P7991 [USACO21DEC] Connecting Two Barns S题解

· · 题解

简要题意

给出一个 n 个点 m 条边，编号为 1…N 的无向图，可以以 (i - j)^2 的代价在任意的 i,j 之间连一条边。现在可以进行不超过两次连边操作，求使得 1 和 n 两点连通的最小代价。

思路

明显可以用并查集来记录每一个点分别在哪一个连通块里。

接下来用 f_i 来表示 i 所在的连通块的代表点。

然后对于 1 和 n 两点有两种情况：

  1. 在同一个连通块里。
  2. 在两个不同的连通块里。

情况 1

很明显不需要连任何一条边，所以代价就是 0。

情况 2

可以直接在 f_1 和 f_n 中最近的两点连边，或者通过其他连通块来间接的连接 f_1 和 f_n。

怎么求出最小值？(对于情况2)

可以先处理出哪些点在 f_1 中，哪些点在 f_n 中，分别记录在 S 数组和 E 数组中。

对于每一个连通块 f_i 计算出其与 f_1 和 f_n 通过连一条边连通的最小代价，分别记录在 s[f_i] 和 e[f_i] 中（这里的计算可以通过二分来实现）。

最后最小代价为 \min_{1\le i\le n} s[f_i]+e[f_i]。

AC代码奉上。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 1e5 + 5;

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -f;
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
    return x * f;
}

int t, n, m, fa[maxn], S[maxn], E[maxn];
ll s[maxn], e[maxn];

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

int main() {
    t = read();
    while (t--) {
        memset(s, 0x3f, sizeof(s));
        memset(e, 0x3f, sizeof(e));
        n = read(); m = read();
        for (int i = 1; i <= n; ++i) fa[i] = i;
        for (int i = 1; i <= m; ++i) {
            int x = read(), y = read();
            x = find(x); y = find(y);
            fa[x] = y;
        }
        if (find(1) == find(n)) {
            printf("0\n");
            continue;
        }
        int rt1 = find(1), rtn = find(n), ct1 = 0, ctn = 0;
        s[rt1] = 0; e[rtn] = 0;
        for (int i = 1; i <= n; ++i) {
            int fi = find(i);
            if (rt1 == fi) S[++ct1] = i;
            if (rtn == fi) E[++ctn] = i;
        }
        ll ans = 0x3f3f3f3f3f3f3f3f;
        for(int i = 1; i <= n; ++i) {
            int fi = find(i);
            if(fi != rt1) {
                int ub1 = upper_bound(S + 1, S + ct1 + 1, i) - S - 1;
                s[fi] = min(s[fi], (ll)(i - S[ub1]) * (i - S[ub1]));
                if (ub1 < ct1) {
                    ++ub1;
                    s[fi] = min(s[fi], (ll)(i - S[ub1]) * (i - S[ub1]));
                }
            }
            if (fi != rtn) {
                int ubn = upper_bound(E + 1, E + ctn + 1, i) - E;
                e[fi] = min(e[fi], (ll)(i - E[ubn]) * (i - E[ubn]));
                if(ubn > 1) {
                    --ubn;
                    e[fi] = min(e[fi], (ll)(i - E[ubn]) * (i - E[ubn]));
                }
            }
        }
        for(int i = 1; i <= n; ++i) {
            int fi = find(i);
//          printf("@%lld %lld\n", s[fi], e[fi]);
            ans = min(ans, s[fi] + e[fi]);
        }
        printf("%lld\n", ans);
    }
    return 0;
}