题目描述
有一个 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
算法1
(Kruskal经典模板) $O(k)$
感言
作为一个模板党,看了这么多题解都觉得不完美,没有前几道题套板子那么轻松。
故水个套板子做法。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1010*1010, M = 2*1010*1010;
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;
while(~scanf("%d%d%d%d", &x1, &y1, &x2, &y2))
{
int a = (x1-1)*m+y1-1, b = (x2-1)*m+y2-1;
p[find(a)] = find(b);
}
int ans = 0;
//跑纵
for(int i=0; i<(n-1)*m; ++i)
{
int a = find(i), b = find(i+m);
if(a!=b)
{
p[a] = b;
ans++;
}
}
//跑横
for(int i=0; i<n*m; ++i)
{
if(i%m < m-1)//枚举到: 最右列-1 的位置
{
int a = find(i), b = find(i+1);
if(a!=b)
{
p[a] = b;
ans+=2;
}
}
}
printf("%d", ans);
return 0;
}
大佬,下标从1开始,怎么调都调不对,哭了
ohhhh
%%%%%%
orz