这是一道关于图论中最小生成树的问题，使用了Kruskal算法来求解。下面是详细的题解，包括代码逐段分析以及时间复杂度和空间复杂度分析。

题目分析

题目给定一个 (m) 行 (n) 列的点阵，点与相邻点可相连，纵向连线花费1个单位，横向连线花费2个单位，部分点之间已有连线，要求计算使所有点全部连通的最少花费。可以将点阵中的点看作图的节点，点之间的连线看作边，已有的连线视为权重为0的边，从而转化为求图的最小生成树问题。

代码逐段分析

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010, M = N * N, K = 2 * N * N;

int n, m, k;
int ids[N][N];
struct Edge
{
    int a, b, w;
}e[K];
int p[M];

• 引入必要的头文件，cstring用于字符串操作（这里主要是memset函数，本题未用），iostream用于输入输出，algorithm用于排序等操作。
• 定义常量N表示点阵的最大行数或列数，M表示节点的最大数量（即 (N * N) ），K表示边的最大数量（ (2 * N * N) ）。
• 声明变量n和m分别记录点阵的行数和列数，k用于记录边的数量。
• 二维数组ids[N][N]用于给每个点分配一个唯一的编号。
• 结构体Edge定义了边的信息，包括两个端点a和b以及边的权重w，数组e[K]用于存储所有的边。
• 数组p[M]用于实现并查集，记录每个节点的父节点。

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

• 实现并查集的find函数，用于查找节点x的根节点。采用路径压缩的方式，即如果当前节点的父节点不是自身，就将其指向根节点，这样后续查找效率更高。

void get_edges()
{
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}, dw[4] = {1, 2, 1, 2};

    for (int z = 0; z < 2; z ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ )
                for (int u = 0; u < 4; u ++ )
                    if (u % 2 == z)
                    {
                        int x = i + dx[u], y = j + dy[u], w = dw[u];
                        if (x && x <= n && y && y <= m)
                        {
                            int a = ids[i][j], b = ids[x][y];
                            if (a < b) e[k ++ ] = {a, b, w};
                        }
                    }
}

• get_edges函数用于生成所有可能的边：
  • 定义了四个数组dx、dy、dw，分别表示在四个方向上的坐标偏移量和对应的边权重（纵向为1，横向为2）。
  • 四层循环遍历点阵中的每个点以及其四个方向。通过z和u % 2 == z的条件，分别处理纵向和横向的边。
  • 对于每个方向，如果目标点在点阵范围内，就获取当前点和目标点的编号a和b，将符合条件（a < b，避免重复记录边）的边信息存储到e数组中，并增加边的数量k。

int main()
{
    cin >> n >> m;

    for (int i = 1, t = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++, t ++ )
            ids[i][j] = t;

    for (int i = 1; i <= n * m; i ++ ) p[i] = i;

    int x1, y1, x2, y2;
    while (cin >> x1 >> y1 >> x2 >> y2)
    {
        int a = ids[x1][y1], b = ids[x2][y2];
        p[find(a)] = find(b);
    }

    get_edges();

    int res = 0;
    for (int i = 0; i < k; i ++ )
    {
        int a = find(e[i].a), b = find(e[i].b), w = e[i].w;
        if (a != b)
        {
            p[a] = b;
            res += w;
        }
    }

    cout << res << endl;

    return 0;
}

• 在main函数中：
  • 首先读取点阵的行数n和列数m。
  • 前两个嵌套循环给点阵中的每个点分配一个唯一编号，存储在ids数组中。
  • 初始化并查集，将每个节点的父节点设为自身。
  • 接着不断读取已有的连线信息，获取对应点的编号a和b，通过并查集将这两个点所在的集合合并。
  • 调用get_edges函数生成所有可能的边。
  • 遍历所有的边，对于每条边，查找其两个端点在并查集中的根节点a和b，如果根节点不同，说明这条边不会形成环，可以加入到最小生成树中，将两个集合合并，并将边的权重累加到结果res中。
  • 最后输出最小花费res，程序结束。

时间复杂度分析

1. 给点编号和初始化并查集的时间复杂度为 (O(nm))。
2. 读取已有连线并进行并查集合并操作，最多有10000条已有连线，每次合并操作时间复杂度近似为 (O(\alpha(nm)))（(\alpha) 为阿克曼函数的反函数，在实际应用中几乎为常数），这部分时间复杂度近似为 (O(10000))。
3. get_edges函数生成边的时间复杂度为 (O(nm))。
4. 对边进行遍历并查集操作，边最多有 (K = 2 * N * N) 条，每次操作时间复杂度近似为 (O(\alpha(nm)))，这部分时间复杂度为 (O(2 * N * N))。

综合来看，总的时间复杂度为 (O(nm))。

空间复杂度分析

1. 存储节点编号的二维数组ids[N][N]，空间复杂度为 (O(nm))。
2. 存储边信息的数组e[K]，空间复杂度为 (O(nm))。
3. 并查集数组p[M]，空间复杂度为 (O(nm))。

因此，总的空间复杂度为 (O(nm))。