$$\color{Red}{连接格点【kruskal】-二维格点化一维}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

题目介绍

有一个 m 行 n 列的点阵，相邻两点可以相连。

一条纵向的连线花费一个单位，一条横向的连线花费两个单位。

某些点之间已经有连线了，试问至少还需要花费多少个单位才能使所有的点全部连通。

输入格式

第一行输入两个正整数 m 和 n 。

以下若干行每行四个正整数 x1,y1,x2,y2，表示第 x1 行第 y1 列的点和第 x2 行第 y2 列的点已经有连线。

输入保证 |x1−x2| + |y1−y2| = 1。

输出格式

输出使得连通所有点还需要的最小花费。

数据范围

1 ≤ m, n ≤ 1000

0 ≤ 已经存在的连线数 ≤ 10000

输入样例：

2 2
1 1 2 1

输出样例：

3

一般ACM或者笔试题的时间限制是1秒或2秒。在这种情况下，代码中的操作次数控制在 10 ^ 7 ∼ 10 ^ 8 为最佳。

n <= 100 -> O(n ^ 3) -> 状态压缩dp floyd 高斯消元

n <= 1000 -> O(n ^ 2) O(n ^ 2 * log(n)) -> dp，二分，朴素版Dijkstra、朴素版Prim、Bellman-Ford

n ≤ 100000 -> O(nlogn) -> 各种sort，线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap、prim+heap、Kruskal、spfa

我的SPFA全题解

我的Dijkstra全题解

我的Bellman_fold全题解

我的Floyd全题解

我的Prim题解

我的Kruskal题解

解析

这道题和之前的最小生成树的问题不同点在于，它是在一个已经有边的二维矩阵图中，已知建边的权重，来计算最小生成树，而并没有预先把边都连好，找最小，需要我们自己建边。

之前学蛇形矩阵和八数码，想必都不陌生一个做法，即二维和一维数据的位置转换。

一个 n * m 的 二维矩阵

二维转一维
(x, y) -> (x - 1) * m + y

一维转二维
x -> (x / m, x % m) 

这道题最多 1000000条边，而边权只有 1 和 2 ，排序其实有些浪费时间，如果是多组数据可能出现过不了的情况，而为了算最小，我们肯定是优先连短的，所以我们分别根据纵向和横向建边。

避免了排序的同时，也不需要改动 kruskal 算法，因为这个算法在已经在一个联通块的时候，不会进行连接。

而为了枚举每个纵向或者横向边，可以像y总一样，利用偏移量枚举的方法，这里可以进一步只用判断一个点右边和下边的点，这样避免判断重边。

但是更简洁，可以直接利用坐标的性质，枚举纵向边，就计算第二个点只计算单一方向的上边的点或下边的点，然后改变一个单位长度for循环的区间【防止越界】

然后并查集的过程，完全不需要进行改造，照搬即可。

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    static int N = 1010, M = N * N;
    static int n, m, cnt;

    static class Node {
        int a, b, w;

        public Node(int a, int b, int w) {
            this.a = a;
            this.b = b;
            this.w = w;
        }
    }

    static int[] p = new int[M];

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

    static boolean merge(int x, int y) {
        int a = find(x), b = find(y);
        if (a != b) {
            p[a] = b;
            return true;
        }
        return false;
    }

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);

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

        // 先把预设的边相连 边权不加入答案
        while (true) {
            String str = br.readLine();
            if (str == null) break;
            String[] s2 = str.split(" ");
            int x1 = Integer.parseInt(s2[0]);
            int y1 = Integer.parseInt(s2[1]);
            int x2 = Integer.parseInt(s2[2]);
            int y2 = Integer.parseInt(s2[3]);
            int a = (x1 - 1) * m + y1, b = (x2 - 1) * m + y2;
            merge(a, b);
        }

        int res = 0;
        // 枚举纵向边
        for (int i = 2; i <= n; i ++)
            for (int j = 1; j <= m; j ++){
                int a = (i - 1) * m + j, b = (i - 2) * m + j;
                if (merge(a, b))
                    res ++;
            }
        // 枚举横向边
        for (int i = 1; i <= n; i ++)
            for (int j = 1; j < m; j ++){
                int a = (i - 1) * m + j, b = a + 1;
                if (merge(a, b))
                    res += 2;
            }

        System.out.println(res);
    }
}