P1105 连接格点

描述

有一个M行N列的点阵，相邻两点可以相连。一条纵向的连线花费一个单位，一条横向的连线花费两个单位。某些点之间已经有连线了，试问至少还需要花费多少个单位才能使所有的点全部连通。
格式

输入格式

第一行输入两个正整数m和n。(m，n≤1000)
以下若干行每行四个正整数x1,y1,x2,y2，表示第x1行第y1列的点和第x2行第y2列的点已经有连线。输入保证|x1−x2|+|y1−y2|=1。

输出格式

输出使得连通所有点还需要的最小花费。

样例

输入样例

2 2

1 1 2 1

输出样例

3

思路：

将矩阵的位置按照从左到右，从上到下进行排序得到点

这样的点就是一维的了，点连接是图，只不过这一次的图是一个矩形；
坑点：这个数据m,n<=1000，就要注意一下了。那么最多可能有1000000个点，那么，我所用的保存edge边的信息的结构体就可能有3000000或者4000000个信息，然后我以为这个数太大了，数组或者结构体会爆炸，sort不能用，结果居然可以
跨考小白有话说：欢迎大家说说更好的方法让我借鉴一下
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <math.h>
using namespace std;
//todo 连接格点    将矩阵的位置按照从左到右，从上到下进行排序得到点
int f[1000002];
struct node
{
    int u, v, w;
} edge[4000002]; //!定义边的信息    注意这里的数据大小
int m, n, r1, r2, s1, s2, z = 0, ans = 0;
find(int x)
{
    if (f[x] != x)
    {
        return find(f[x]);
    }
    else
    {
        return x;
    }
}
bool cmp(node a, node b)
{
    return a.w < b.w;
}
int main()
{
    scanf("%d", &m);
    scanf("%d", &n);
    for (int i = 1; i <= m * n; i++) //*初始化并查集
    {
        f[i] = i;
    }
    for (int i = 1; i <= m; i++) //*初始化横向权值
    {
        for (int j = 1; j < n; j++)
        {
            int x = (i - 1) * n + j;
            int y = x + 1;
            edge[++z].u = x;
            edge[z].v = y;
            edge[z].w = 2;
        }
    }
    for (int i = 1; i <= n; i++) //*初始化纵向权值
    {
        for (int j = 1; j < m; j++)
        {
            int x = (j - 1) * n + i;
            int y = x + n;
            edge[++z].u = x;
            edge[z].v = y;
            edge[z].w = 1;
        }
    }
    while (scanf("%d%d%d%d", &r1, &s1, &r2, &s2) != EOF) //*同上
    {
        int x = (r1 - 1) * n + s1;
        int y = (r2 - 1) * n + s2;
        edge[++z].u = x;
        edge[z].v = y;
        edge[z].w = 0;
    }
    sort(edge + 1, edge + 1 + z, cmp); //*对边进行排序
    for (int i = 1; i <= z; i++)       //*merge  kruskal算法
    {
        int a = find(edge[i].u);
        int b = find(edge[i].v);
        if (a != b)
        {
            f[a] = b;
            ans += edge[i].w;
        }
    }
    printf("%d\n", ans);
    return 0;
}

Kruskal(缩点) + 并查集 - 连接格点 - AcWing 1144
有一个 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


分析：
$首先将已经连接好的点加入到对应的连通块中，接着在各个连通块之间跑最小生成树即可。$
$主要问题有：$
$①、二维坐标点转化到一维坐标上去，方便建图。$
$②、各点与相邻点之间的边如何建立。$
$\qquad事实上，只要把点都加入连通块中去即可，故每条无向边我们仅需建立一次。$
$\qquad为了节约空间，我们对每个点，将该点与其相邻的右、下两个点建立一条边。$
$③、本题最多有n×m条边，极限在10^6级别。排序的话时间限制仍然较紧。$
$\qquad但是我们发现，边权仅有1和2两种情况，故我们可以优先建立边权为1的竖边。$
$\qquad这仅需在循环所有点建图的时候循环两次，第一次建立每个点下方的边，第二次建立右方的边。$
$\qquad这就把求最小生成树的时间复杂度优化到了O(M)，其中M=n×m，即边的数量。$
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=1010, M=N*N, K=2*M;

int n,m,res,ecnt;
int p[M];
int ids[N][N];
struct edge
{
    int u,v,w;
}E[K];

int Find(int x)
{
    if(p[x]!=x) return p[x]=Find(p[x]);
    return p[x];
}

void get_edges()
{
    int dir[2][2]{{1,0},{0,1}}, w[2]={1,2};  //一条边加一次就行，防数组越界，对每个点加右、下两条边
    
    for(int z=0;z<2;z++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                int x=i+dir[z][0],y=j+dir[z][1];
                if(x>0&&x<=n&&y>0&&y<=m)
                {
                    int a=ids[i][j],b=ids[x][y];
                    E[ecnt++]={a,b,w[z]};   
                }
            }
}

void kruskal()
{
    int a,b;
    for(int i=0;i<ecnt;i++)
    {
        a=Find(E[i].u),b=Find(E[i].v);
        if(a!=b)
        {
            p[a]=b;
            res+=E[i].w;
        }
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n*m;i++) p[i]=i;
    
    for(int i=1,idx=0;i<=n;i++)
        for(int j=1;j<=m;j++)
            ids[i][j]=++idx;
            
    int x0,y0,x2,y2;
    while(~scanf("%d%d%d%d",&x0,&y0,&x2,&y2))
    {
        int a=ids[x0][y0],b=ids[x2][y2];
        a=Find(a),b=Find(b);
        p[a]=b;
    }
    
    get_edges();
    
    kruskal();
    
    cout<<res<<endl;
    
    return 0;
}

连接格点
描述
有一个M行N列的点阵，相邻两点可以相连。一条纵向的连线花费一个单位，一条横向的连线花费两个单位。某些点之间已经有连线了，试问至少还需要花费多少个单位才能使所有的点全部连通。
输入
第一行输入两个正整数m和n, 其中 1 <= n,m <= 1000。
以下若干行每行四个正整数x1,y1,x2,y2，表示第x1行第y1列的点和第x2行第y2列的点已经有连线。输入保证|x1-x2|+|y1-y2|=1。
输出
输出使得连通所有点还需要的最小花费。
输入样例 1
2 2

1 1 2 1
输出样例 1
3
此题使用并查集，最好用图表的形式来写。

重要信息：

某些点之间已经有连线了，试问至少还需要花费多少个单位才能使所有的点全部连通
以下若干行每行四个正整数x1,y1,x2,y2，表示第x1行第y1列的点和第x2行第y2列的点已经有连线。输入保证|x1-x2|+|y1-y2|=1。
输出使得连通所有点还需要的最小花费。

因为这道题格点为重要信息，因此，你最先想到的肯定是二维数组。

二维数组图表：



这就只能用（x,y）的坐标来表示了，所以要用pair来写。但是，你是否想过，这会处理很长的一片。

因此，我们用一维数组更好一些。

但是，我们要怎么表示呢？——标记

如图：


很简单，我们将行和列的数字一 一标记，这样，我们就方便了很多。

一个问题，因为标记了，就是去了二维数组查找的功能，怎么办？
x*m+y

这是一个算术，我们用这个来表示位置。（但这是从2开始找的，习惯从1开始找，就改变成x*m+y-m）最好用函数来表示。

实现此结构：
int convert(int x,int y){
	return x*m+y-m;
}

中间使用函数初始化：
void init(){
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			fa[convert(i,j)]=convert(i,j);
		}
	}
}

然后，我们就要处理并查集的结构了：
int get(int x){
	if(fa[x]==x){
		return x;
	}
	fa[x]=get(fa[x]);
	return fa[x];
}
void merge(int x,int y){
	fa[get(x)]=get(y);
}

接下来，在main函数里写下：
while(cin>>a>>b>>c>>d){
		merge(convert(a,b),convert(c,d));
}

merge用来合并两个点，就变成了线。

接下来处理行（m为行，n为列）：
for(int j=1;j<=n;j++){
		for(int i=1;i+1<=m;i++){
			if(get(convert(i,j))!=get(convert(i+1,j))){
				merge(get(convert(i,j)),get(convert(i+1,j)));
				ans++;
			}
		}
	}

这样，使行后面就合并了，如果他们不相等，就无法连接，于是就然他们是连接的。统计行的个数。

接下来统计列：
for(int i=1;i<=m;i++){
		for(int j=1;j+1<=n;j++){
			if(get(convert(i,j))!=get(convert(i,j+1))){
				merge(get(convert(i,j)),get(convert(i,j+1)));
				ans+=2;
			}
		}
	}

与行类似，但这里每次加两次，因为列上在数组里有2n次。

注意，范围大，数组要超过1000000。

实现代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=10000010;
int m,n;
long long a,b,c,d;
long long fa[maxn];
int convert(int x,int y){
	return x*m+y-m;
}
void init(){
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			fa[convert(i,j)]=convert(i,j);
		}
	}
}
int get(int x){
	if(fa[x]==x){
		return x;
	}
	fa[x]=get(fa[x]);
	return fa[x];
}
void merge(int x,int y){
	fa[get(x)]=get(y);
}
int main(){
	cin>>m>>n;
	init();
	long long ans=0;
	while(cin>>a>>b>>c>>d){
		merge(convert(a,b),convert(c,d));
	}
	for(int j=1;j<=n;j++){
		for(int i=1;i+1<=m;i++){
			if(get(convert(i,j))!=get(convert(i+1,j))){
				merge(get(convert(i,j)),get(convert(i+1,j)));
				ans++;
			}
		}
	}
	for(int i=1;i<=m;i++){
		for(int j=1;j+1<=n;j++){
			if(get(convert(i,j))!=get(convert(i,j+1))){
				merge(get(convert(i,j)),get(convert(i,j+1)));
				ans+=2;
			}
		}
	}
	cout<<ans;
	return 0;
}

作者:rebirth.death

山再高，往上爬，总能登顶；

路再长，走下去，定能到达。
链接各点
题目描述

有一个M行N列的点阵，相邻两点可以相连。一条纵向的连线花费一个单位，一条横向的连线花费两个单位。某些点之间已经有连线了，试问至少还需要花费多少个单位才能使所有的点全部连通。

输入

第一行输入两个正整数m和n。

以下若干行每行四个正整数x1,y1,x2,y2，表示第x1行第y1列的点和第x2行第y2列的点已经有连线。输入保证|x1-x2|+|y1-y2|=1。

输出

输出使得连通所有点还需要的最小花费。

Sample Input

2 2

1 1 2 1

Sample Output

3

Hint

30%数据：n*m<=1000

100%数据：m,n<=1000

题解分析

首先用一张动态图描写思路



首先因为竖着连的价格最小，所以先竖着连如果这两个点不在一个树内，即根不相同那么就把这两个链接，如图所示。

走完竖向之后走横向，就像图像所示，如果发现这两个的根是一个，那么就不连接，如果不是就连接。
但是这个是二维的并查集怎么办呢，其实这和一维的没有区别，咱们只需要确定好坐标，有点哈希的意思 就可以了。

咱们可以这样编号，以此图为例

1   2   3   4   5

6   7   8   9   10

11 12 13 14 15

16 17 18 19 20

21 22 23 24 25

是不是一下子就知道怎么肥4了

好嘞，这样我们就可以AC了

AC时间到
PS注意不要数指针漂移也不要数组越界。

数组至少开到1001*1001吧
#include<unordered_map>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<utility>
#include<stdio.h>
#include<vector>
#include<string>
#include<math.h>
#include<cmath>
#include<queue>
#include<stack>
#include<deque>
#include<map>
#pragma warning(disable:4244)
#define PI 3.1415926536
#pragma GCC optimize(2)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll ll_inf = 9223372036854775807;
const int int_inf = 2147483647;
const short short_inf = 32767;
const char char_inf = 127;
inline ll read() {
    ll c = getchar(), Nig = 1, x = 0;
    while (!isdigit(c) && c != '-')c = getchar();
    if (c == '-')Nig = -1, c = getchar();
    while (isdigit(c))x = ((x << 1) + (x << 3)) + (c ^ '0'), c = getchar();
    return Nig * x;
}
inline void out(ll a)
{
    if (a < 0)putchar('-'), a = -a;
    if (a >= 10)out(a / 10);
    putchar(a % 10 + '0');
}
ll qpow(ll x, ll n, ll mod) {
    ll res = 1;
    while (n > 0) {
        if (n & 1)res = (res * x) % mod;
        x = (x * x) % mod; n >>= 1;
    }
    return res;
}
#define read read()
int fa[1010025];
int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void merge(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx != fy)fa[fx] = fy;
}
int main()
{
    for (int i = 1; i < 1010025; i++)fa[i] = i;
    int x = read, y = read;
    int x1, x2, y1, y2;
    int tot = 0;
    int num1, num2;
    while (scanf("%d%d%d%d", &x1, &y1, &x2, &y2) != EOF)
    {
        num1 = (x1 - 1) * y + y1;
        num2 = (x2 - 1) * y + y2;
        merge(num1, num2);
    }
    for (int j = 1; j <= y; j++)
        for (int i = 1; i < x; i++)
        {
            num1 = (i - 1) * y + j;
            num2 = num1 + y;
            if (find(num1) != find(num2))
            {
                tot++;
                merge(num1, num2);
            }
        }
    for (int i = 1; i <= x; i++)
        for (int j = 1; j < y; j++)
        {
            num1 = (i - 1) * y + j;
            num2 = num1 + 1;
            if (find(num1) != find(num2))
            {
                tot += 2;
                merge(num1, num2);
            }
        }
    cout << tot << endl;
}

By-轮月