连接格点(grid)

题目描述

有一个 $m$ 行 $n$ 列的点阵，相邻两点可以相连：纵向连线花费 $1$ 个单位，横向连线花费 $2$ 个单位。某些点之间已经有连线了，求至少还需花费多少个单位才能使所有点连通。输入第一行两个正整数 $m$ 和 $n$ ；以下若干行每行四个正整数 $x_1, y_1, x_2, y_2$ ，表示第 $x_1$ 行第 $y_1$ 列的点与第 $x_2$ 行第 $y_2$ 列的点已有连线，保证 $|x_1-x_2|+|y_1-y_2|=1$ 。输出最小花费。 $100\%$ 数据： $m, n \le 1000$ 。

input

1
22 2
1 1 2 1

样例输入输出：输入 2 2 与连线 1 1 2 1，输出 3。

思路

把格点看作点：已有连线边权 $0$ 、纵向边权 $1$ 、横向边权 $2$ ，答案就是这张图的最小生成树。边权只有 $0/1/2$ 三种，无需排序，按 Kruskal 贪心顺序分三阶段做并查集：先合并全部已有连线，再扫描所有纵向边，最后扫描所有横向边，两端不连通就合并并累加对应花费。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-04-18 10:00
# update_at: 2026-04-18 10:00

import sys


def find_root(parent: list[int], x: int) -> int:
    """查询节点 x 所在集合的代表元，带路径压缩。"""
    curr = x
    while parent[curr] != curr:
        curr = parent[curr]
    while parent[x] != curr:
        parent[x], x = curr, parent[x]
    return curr


def try_union(parent: list[int], u: int, v: int) -> bool:
    """若 u 和 v 尚未连通则合并并返回 True，否则返回 False。"""
    root_u, root_v = find_root(parent, u), find_root(parent, v)
    if root_u == root_v:
        return False
    parent[root_v] = root_u
    return True


def solve() -> None:
    tokens = sys.stdin.buffer.read().split()
    if not tokens:
        return
    data = iter(map(int, tokens))
    m, n = next(data), next(data)

    parent = list(range(m * n))

    # 预连接已存在的无费用边
    for x1 in data:
        y1, x2, y2 = next(data), next(data), next(data)
        u = (x1 - 1) * n + (y1 - 1)
        v = (x2 - 1) * n + (y2 - 1)
        try_union(parent, u, v)

    # 优先贪心选择花费为 1 的所有纵向边
    vertical_cost = sum(
        1
        for c in range(n)
        for r in range(m - 1)
        if try_union(parent, r * n + c, (r + 1) * n + c)
    )

    # 再贪心选择花费为 2 的所有横向边
    horizontal_cost = sum(
        2
        for r in range(m)
        for c in range(n - 1)
        if try_union(parent, r * n + c, r * n + c + 1)
    )

    print(vertical_cost + horizontal_cost)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 12:44
 * update_at: 2026-10-05 12:44
 */

#include <cstdio>

typedef long long ll;

const int MAXN = 1005; // 行列上限 1000，开 1005 防越界
const int MAXV = MAXN * MAXN;

int m, n;           // m 行 n 列的点阵
ll cost;            // 还需要的最小花费
int fa[MAXV];       // fa[i]：点 i（编号 (行-1)*n + 列-1）所在并查集的父节点

// 查找点 x 的根，带路径压缩
int find_root(int x) {
    int root = x;
    while (fa[root] != root)
        root = fa[root];
    while (fa[x] != root) {
        int nxt = fa[x];
        fa[x] = root;
        x = nxt;
    }
    return root;
}

// 若 u、v 尚未连通则合并并返回 true，否则返回 false
bool try_union(int u, int v) {
    int ru = find_root(u);
    int rv = find_root(v);
    if (ru == rv)
        return false;
    fa[ru] = rv;
    return true;
}

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

    // 初始化并查集
    for (int i = 0; i < m * n; ++i)
        fa[i] = i;

    // 已有连线花费为 0，先全部合并
    int x1, y1, x2, y2;
    while (scanf("%d %d %d %d", &x1, &y1, &x2, &y2) == 4) {
        int u = (x1 - 1) * n + (y1 - 1);
        int v = (x2 - 1) * n + (y2 - 1);
        try_union(u, v);
    }

    // 阶段一：先加花费 1 的纵向边 ((r,c),(r+1,c))，能合并就累加 1
    for (int r = 0; r < m - 1; ++r)
        for (int c = 0; c < n; ++c)
            if (try_union(r * n + c, (r + 1) * n + c))
                cost += 1;

    // 阶段二：再加花费 2 的横向边 ((r,c),(r,c+1))，能合并就累加 2
    for (int r = 0; r < m; ++r)
        for (int c = 0; c < n - 1; ++c)
            if (try_union(r * n + c, r * n + c + 1))
                cost += 2;

    printf("%lld\n", cost);
    return 0;
}

目录

题目描述

思路

参考代码