连接格点

1.二维数组一维化的并查集

因为本题的节点信息都是二维的，例如(1,2),(2,3)，而传统的并查集都是一维节点编号下的。本题的解决策略为，通过将二维数组展成一维数组，然后通过行号i和列号j求出二维数组的点(i,j)在一维平面的映射，进而求的相应的关系。

//其中i代表坐标所在的行号,j代表坐标所在的列号,n代表整个地图的列数
int index = (i - 1) * n + j 

2.最小生成树建树策略：

据题意可知，横边的代价为2，竖边的代价为1，因此，在最后的连通区域中横边越少越好，竖边越多越好。因此可以先根据竖边建树，然后再根据横边把没法连通的点连起来，这样的代价即为最小代价。

3.朴素规律：

已知一个地图是m行，n列，那么如果想要把所有的点连通，最小的代价为n-1条横边 + (m-1)*n条竖边，据此可以分析出另一种思路：

先统计出连接好的边有几条横的，几条竖的，然后通过数学计算直接求出最小代价。

基于思路一、二的代码：

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

using namespace std;

const int N = 2000;

int f[N*N];
int m, n;
int x1, y1, x2, y2;

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

int merge(int x, int y)
{
    int fx = find(x), fy = find(y);
    if(fx != fy)
    {
        f[fy] = fx;
        return 1;
    }
    return 0;
}

int main()
{
    scanf("%d%d", &m, &n);
    for(int i = 1; i <= n * m; i ++)
        f[i] = i;
    while(~scanf("%d%d%d%d", &x1, &y1, &x2, &y2))
    {
        int t1 = n * (x1 - 1) + y1, t2 = n * (x2 - 1) + y2;
        merge(t1, t2);
    }

    int res = 0;
    for(int i = 1; i <= n; i ++ )
    {
        for(int j = 1; j < m; j ++ )
        {
            int t1 = (j - 1) * m + i, t2 = j * m + i;
            if(merge(t1, t2))
                res ++;
        }
    }

    for(int i = 1; i <= m; i ++ )
    {
        for(int j = 1; j < n; j ++ )
        {
            int t1 = (i - 1) * m + j, t2 = (i - 1) * m + j + 1;
            if(merge(t1, t2))
                res += 2;
        }
    }

    printf("%d",res);

    return 0;
}