1144. 连接格点，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

 解析：AcWing 1144. 连接格点（算法提高课） - AcWing

 

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>using namespace std;
typedef long long LL;
const int N = 1e3+10, M = 2 * N * N;
int n, m,k;int fa[N * N],idx[N][N];
struct st {int a, b, c;
}e[M];int find(int a) {if (fa[a] == a)return fa[a];return fa[a] = find(fa[a]);
}void get() {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 = idx[i][j], b = idx[x][y];if (a < b)e[++k] = { a,b,w };}}}}}}
}int main() {cin >> n >> m;for (int i = 1,t=1; i <= n; i++) {for (int j = 1; j <= m; j++,t++) {idx[i][j] = t;}}for (int i = 1; i <= n * m; i++)fa[i] = i;int x1, y, x2, y2;while (cin >> x1 >> y >> x2 >> y2) {fa[find(idx[x1][y])] = find(idx[x2][y2]);}get();int ans = 0;for (int i = 1; i <= k; i++) {int a = find(e[i].a), b = find(e[i].b), w = e[i].c;if (a != b) {fa[a] = b;ans += w;}}cout << ans << endl;return 0;
}