A28832. 连接格点(grid)
填空题
困难
知识点
题目描述
连接格点(grid)
题目描述
有一个M行N列的点阵，相邻两点可以相连。一条纵向的连线花费一个单位，一条横向的连线花费两个单位。某些点之间已经有连线了，试问至少还需要花费多少个单位才能使所有的点全部连通。
输入
第一行输入两个正整数m和n。
以下若干行每行四个正整数x1,y1,x2,y2，表示第x1行第y1列的点和第x2行第y2列的点已经有连线。输入保证|x1−x2|+|y1−y2|=1。
输出
输出使得连通所有点还需要的最小花费。
输入样例
2 2
1 1 2 1输出样例
3提示
数据规模
30%数据：n×m≤1000；
100%数据：m,n≤1000。
参考答案
#include<bits/stdc++.h>
using namespace std;
#define N 1000005
struct Edge
{
int u, v, w;
bool operator < (const Edge &b) const
{
return w < b.w;
}
};
int m, n, fa[N], ans;
vector<Edge> edges;
void initFa(int n)
{
for(int i = 0; i <= n; ++i)
fa[i] = i;
}
int find(int x)
{
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void merge(int x, int y)
{
fa[find(x)] = find(y);
}
void kruskal()
{
sort(edges.begin(), edges.end());
for(Edge e : edges)
{
int u = e.u, v = e.v, w = e.w;
if(find(u) != find(v))
{
merge(u, v);
ans += w;
}
}
}
int nodeNum(int x, int y)//将坐标转为顶点编号
{//x-1、y-1变为从0开始的行号和列号
return (x-1)*n+(y-1);//在第x-1行(从0开始)，其上已经有(x-1)*n个元素，第y-1列，就是这一行已经过了y个元素，当前元素是从0开始的第(x-1)*n+y-1个元素
}
int main()
{
cin >> m >> n;
initFa(m*n);//共m*n个顶点
int x1, y1, x2, y2;
for(int x = 1; x <= m; ++x)
for(int y = 1; y <= n; ++y)
{
if(x+1 <= m)
edges.push_back(Edge{nodeNum(x, y), nodeNum(x+1, y), 1});//一条竖线
if(y+1 <= n)
edges.push_back(Edge{nodeNum(x, y), nodeNum(x, y+1), 2});//一条横线
}
while(cin >> x1 >> y1 >> x2 >> y2)
merge(nodeNum(x1, y1), nodeNum(x2, y2));
kruskal();
cout << ans;
return 0;
}
上一题
下一题