题解 | 连线问题

题目回顾(简短回顾一波～)

有两条平行的直线：

• 第一条：$x = A$，上面有 $n$ 个点；
• 第二条：$x = B$，上面有 $m$ 个点。

给出它们纵坐标的差分数组（即相邻点的间距）， 求让这两条线上所有点联通的最小总代价。

两点之间的代价是欧几里得距离：

$$\text{dist} = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2} $$

---

数据格式

输入：

n m A B
a[2] ... a[n]
b[2] ... b[m]

• a[i] 是第 $i$ 点与第 $i-1$ 点的纵向间距。
• b[j] 同理。
• 纵坐标可通过前缀和还原。

---

思路分析

一、核心思想：最小生成树（MST）

我们希望让两条线上的所有点连通且总代价最小。 这正是一个最小生成树Minimum Spanning Tree, MST问题。

---

二、节点与边的构造

节点

• 左边线 $x = A$ 上有 $n$ 个节点：编号 $1$ ~ $n$；
• 右边线 $x = B$ 上有 $m$ 个节点：编号 $n+1$ ~ $n+m$。

边

三类边：

同一条线上相邻点的边

• 竖直边
• 权值 = 间距
• 必定属于最优解（因为最短）

2️ 跨线最近点之间的边

• 对每个左边点，找到右边线中纵坐标最接近的点（lower_bound）；
• 加入它与上下相邻点的连线；
• 边权 = 欧几里得距离。

这样就能保证边集规模约为$(O(n+m))$。

---

三、Kruskal 求最小生成树

1. 将所有边按权值升序排序；
2. 用并查集（Union-Find）维护连通性；
3. 依次选取最小的边，若连接了不同的连通块，就加入生成树；
4. 累加边权，得到最小代价。

---

代码讲解

#include <bits/stdc++.h>
#define MAXN 2400005
using namespace std;
#define ll long long

int n, m, A, B;
int a[MAXN], b[MAXN];

double dis(int i, int j) {
    // 欧几里得距离计算
    return sqrt((ll)(a[i] - b[j]) * (a[i] - b[j]) + (ll)(A - B) * (A - B));
}

struct edge {
    int u, v; double w;
    edge(int u=0, int v=0, double w=0):u(u), v(v), w(w){}
    bool operator < (const edge &e1) const { return w < e1.w; }
} e[MAXN];

int top = 0;
int fa[MAXN];

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

double merge(int u, int v, double w) {
    int ru = findR(u), rv = findR(v);
    if (ru == rv) return 0;
    fa[ru] = rv;
    return w;
}

int main() {
    scanf("%d%d%d%d", &n, &m, &A, &B);

    // 输入第1条线
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        fa[i] = i;
        if (i > 1) {
            // 相邻两点连边（竖直边）
            e[++top] = edge(i - 1, i, a[i]);
            a[i] += a[i - 1]; // 前缀和恢复纵坐标
        }
    }

    // 输入第2条线
    for (int j = 1; j <= m; j++) {
        scanf("%d", &b[j]);
        fa[n + j] = n + j;
        if (j > 1) {
            e[++top] = edge(n + j - 1, n + j, b[j]);
            b[j] += b[j - 1];
        }
    }

    // 跨线连边：左边每个点 -> 右边最近点
    for (int i = 1; i <= n; i++) {
        int j = lower_bound(b + 1, b + 1 + m, a[i]) - b;
        if (j > 1) e[++top] = edge(i, n + j - 1, dis(i, j - 1));
        if (j <= m) e[++top] = edge(i, n + j, dis(i, j));
    }

    // Kruskal
    sort(e + 1, e + 1 + top);
    double ans = 0;
    for (int i = 1; i <= top; i++)
        ans += merge(e[i].u, e[i].v, e[i].w);

    printf("%.2f\n", ans);
    return 0;
}

---

(这代码， 应该是个人都能看懂把）

复杂度分析

(这个是蒟蒻最不喜欢弄得)

步骤	复杂度
建图	$O(n + m)$
排序	$O((n+m) log(n+m))$
并查集	$O(α(n+m))$ ≈ 常数
总体	$O((n+m) log(n+m))$

---

---

小结

题目本质：

「最小生成树（MST） + 坐标还原 + 剪枝优化」

关键优化：

• 不用全连接，只取每个点在另一条线上的最近点；
• 使用 lower_bound 实现快速匹配；
• 结果即为连接两条平行线上所有点的最小总代价。

---