AcWing1144. 连接格点

2022-12-26 17:09:52 来源：博客园

【资料图】

传送门

题目描述

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

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

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

解题思路

\(\qquad\)在输入的时候把已经有连线的点合并到同一个集合(通过并查集)，为了方便并查集的处理，我们将一个坐标点\((x,y)\)做一个映射：变成一维坐标\(x\times m +y\)这样就可以用一维的并查集了。\(\qquad\)对于一开始不连通的点，我们观察边权可以得到一个贪心思路：纵连线一定是比横连线实惠的。所以我们就先连纵的。

\(\qquad\)当我们按照上面的策略连完纵向连线后，相当于得到一个这样的图：\(\LARGE .代表格子，|代表纵向边\)

........（n列）||||||||........||||||||........(m行)

所以这张图只要我们把第一行都连起来，就好了。因此我们采取的策略就是：\(\qquad\)首先按列枚举\(i ->\ (1\sim n)\),\(\qquad\)对于每一列我们再按行枚举\(j->\ (1\sim n-1)\)，然后我们把这列上每一行的格子和它的下一行连线，并将统计的结果\(+1\)（花费），也就是连接坐标点\((j,i)和(j+1,i)\)

\(\qquad\)按列枚举后就是讲第一行的所有点连接了\(\qquad\)这里只需要枚举\(i->(1\sim m-1)\)，连接所有的坐标\((1,i),1(i+1)\)就行

代码

#include #pragma GCC optimize(2)#define x first#define y secondusing namespace std;typedef pair PII;const int N = 1010, M = N * N;int p[M], n, m;int get(int x, int y) { return x * m + y; }struct Edge {    int u, v, w;    bool operator <(const Edge& W) const {        return w < W.w ;    }} edge[M];int find(int x) {    if (x != p[x]) p[x] = find(p[x]);    return p[x];}int main() {    scanf("%d%d", &m, &n);        for (int i = 1; i <= m * m + n; i ++ ) p[i] = i;        int x1, y1, x2, y2;    while (~scanf("%d%d%d%d", &x1, &y1, &x2, &y2))        p[find(get(x1, y1))] = find(get(x2, y2));            int res = 0;    for (int i = 1; i <= n; i ++ )     {        for (int j = 1; j < m; j ++ )        {            int a = find(get(j, i)), b = find(get(j + 1, i));            if (a != b) p[a] = b, res ++ ;        }    }        for (int i = 1; i < n; i ++ )     {        int a = find(get(1, i)), b = find(get(1, i + 1));        if (a != b) p[a] = b, res += 2;    }        printf("%d\n", res);        return 0;}

\(\color{Green}{顺利AC！}\)

关键词：