题解：点阵连通问题

问题描述

给定一个 $m$ 行 $n$ 列的点阵，相邻两点可以相连。纵向连线花费1个单位，横向连线花费2个单位。某些点之间已经存在连线，求至少还需要多少花费才能使所有点全部连通。

方法思路

1. 问题分析：点阵可以视为一个图，每个点是一个节点，相邻点之间有边。已有边相当于已经连通，无需花费。目标是用最小花费添加边使得整个图连通。
2. 关键观察：纵向边花费少（1单位），应优先使用；横向边花费高（2单位），应尽量避免使用。
3. 算法选择：使用并查集来维护连通分量。首先处理已有的边（免费），然后优先添加纵向边（花费1），最后添加横向边（花费2）。
4. 实现细节：
   • 将二维点阵映射为一维索引：点 $(i, j)$ 对应索引 $(i-1)*m + j-1$。
   • 使用并查集合并已有边连接的节点。
   • 遍历所有可能的纵向边（上下相邻），优先合并未连通的组件，花费1单位每条。
   • 遍历所有可能的横向边（左右相邻），合并未连通的组件，花费2单位每条。

解决代码

#include<bits/stdc++.h>
using namespace std;

const int N = 1010 * 1010; // 最大节点数：点阵最大为1000x1000
const int M = 2 * 1010 * 1010; // 最大边数：大约每个点有2条边（纵横）

struct Edge
{
    int a, b, w;

    bool operator <(const Edge& W) const
    {
        return w < W.w;
    }
} edges[M];

int n, m; // 点阵的行数和列数
int p[N]; // 并查集的父节点数组

// 并查集的查找函数，带路径压缩
int find(int x)
{
    if (p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}

int main()
{
    scanf("%d%d", &n, &m);
    int x1, y1, x2, y2;

    // 初始化并查集，每个节点自成一个连通分量
    for (int i = 0; i < n * m; ++i)
        p[i] = i;

    // 处理已有的连线：输入直到EOF，每次读入一条已有的边
    while (~scanf("%d%d%d%d", &x1, &y1, &x2, &y2))
    {
        // 将二维坐标转换为一维索引
        int a = (x1 - 1) * m + y1 - 1;
        int b = (x2 - 1) * m + y2 - 1;
        // 合并这两个点所在的连通分量
        p[find(a)] = find(b);
    }

    int ans = 0; // 记录总花费

    // 优先处理纵向边（花费1）
    // 遍历所有纵向边：第i行和第i+1行的同一列
    for (int i = 0; i < (n - 1) * m; ++i)
    {
        int a = find(i);         // 当前点的根节点
        int b = find(i + m);     // 下方相邻点的根节点
        if (a != b)              // 如果不连通，则连接它们
        {
            p[a] = b;            // 合并
            ans += 1;            // 花费1单位
        }
    }

    // 处理横向边（花费2）
    // 遍历所有横向边：同一行中的相邻列
    for (int i = 0; i < n * m; ++i)
    {
        if (i % m < m - 1)       // 确保不是最后一列（否则没有右邻居）
        {
            int a = find(i);     // 当前点的根节点
            int b = find(i + 1); // 右侧相邻点的根节点
            if (a != b)          // 如果不连通，则连接它们
            {
                p[a] = b;        // 合并
                ans += 2;        // 花费2单位
            }
        }
    }

    printf("%d", ans);

    return 0;
}

代码解释

1. 初始化：并查集数组 p 初始化，每个节点自成一集合。
2. 处理已有边：读取已有连线，合并对应的节点。
3. 添加纵向边：遍历所有上下相邻的点对，若未连通则合并，花费1单位。
4. 添加横向边：遍历所有左右相邻的点对，若未连通则合并，花费2单位。
5. 输出总花费：打印所需的最小花费。

这种方法确保优先使用便宜的纵向边，最小化总花费，高效地解决了问题。