-
连接格点
2020-03-22 21:07:07某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有的点全部连通。 格式 输入格式 第一行输入两个正整数m和n。(m,n≤1000) 以下若干行每行四个正整数x1,y1,x2,y2,表示第x1行第y1列的点和第x2行第y2...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
2020-07-03 00:35:56某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有的点全部连通。 输入格式 第一行输入两个正整数 m 和 n。 以下若干行每行四个正整数 x1,y1,x2,y2,表示第 x1 行第 y1 列的点和第 x2 行第 y2 列的点...Kruskal(缩点) + 并查集 - 连接格点 - AcWing 1144
有一个 m 行 n 列的点阵,相邻两点可以相连。
一条纵向的连线花费一个单位,一条横向的连线花费两个单位。
某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有的点全部连通。
输入格式
第一行输入两个正整数 m 和 n。
以下若干行每行四个正整数 x1,y1,x2,y2,表示第 x1 行第 y1 列的点和第 x2 行第 y2 列的点已经有连线。
输入保证|x1−x2|+|y1−y2|=1。
输出格式
输出使得连通所有点还需要的最小花费。
数据范围
输入样例:
2 2 1 1 2 1
输出样例:
3
分析:
代码:
#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; }
-
题解-连接格点
2019-06-01 14:03:35某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有的点全部连通。 输入 第一行输入两个正整数m和n, 其中 1 <= n,m <= 1000。 以下若干行每行四个正整数x1,y1,x2,y2,表示第x1行第y1列的点和第...连接格点
描述
有一个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
-
UPC-连接格点
2020-03-17 11:29:13某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有的点全部连通。 输入 第一行输入两个正整数m和n。 以下若干行每行四个正整数x1,y1,x2,y2,表示第x1行第y1列的点和第x2行第y2列的点已经有连线。输...山再高,往上爬,总能登顶;
路再长,走下去,定能到达。链接各点
题目描述
有一个M行N列的点阵,相邻两点可以相连。一条纵向的连线花费一个单位,一条横向的连线花费两个单位。某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有的点全部连通。
输入
第一行输入两个正整数m和n。
以下若干行每行四个正整数x1,y1,x2,y2,表示第x1行第y1列的点和第x2行第y2列的点已经有连线。输入保证|x1-x2|+|y1-y2|=1。输出
输出使得连通所有点还需要的最小花费。
Sample Input
2 2
1 1 2 1Sample 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-轮月
-
福大OJ 连接格点
2018-12-18 11:27:54某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有的点全部连通。 Input 第一行输入两个正整数m和n。 以下若干行每行四个正整数x1,y1,x2,y2,表示第x1行第y1列的点和第x2行第y2列的点已经有连线。... -
Acwing1144. 连接格点
2020-09-21 18:59:02某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有的点全部连通。 输入格式 第一行输入两个正整数 m 和 n。 以下若干行每行四个正整数 x1,y1,x2,y2,表示第 x1 行第 y1 列的点和第 x2 行第 y2 列的点... -
AcWing 1144 连接格点
2020-08-09 21:42:58某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有的点全部连通。 输入格式 第一行输入两个正整数m和n。 以下若干行每行四个正整数 x1,y1,x2,y2,表示第x1行第y1列的点和第x2行第y2列的点已经有... -
1144. 连接格点题解
2021-01-27 15:34:57某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有的点全部连通。 输入格式 第一行输入两个正整数 m 和 n。 以下若干行每行四个正整数 x1,y1,x2,y2,表示第 x1 行第 y1 列的点和第 x2 行第 y2 列的点... -
1394:连接格点(grid)
2020-04-27 11:38:13某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有的点全部连通。 【输入】 第一行输入两个正整数m和n。 以下若干行每行四个正整数x1,y1,x2,y2,表示第x1行第y1列的点和第x2行第y2列的点... -
连接格点题解
2017-09-01 16:19:15描述 ...某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有的点全部连通。 输入格式 第一行输入两个正整数m和n。 以下若干行每行四个正整数x1,y1,x2,y2,表示 -
问题 B: 连接格点(并查集)
2020-03-16 21:19:25问题 B: 连接格点(并查集) 题目描述 有一个M行N列的点阵,相邻两点可以相连。...某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有的点全部连通。 输入 第一行输入两个正整数m和n。 以下... -
【模拟试题】连接格点
2017-05-02 17:21:44某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有的点全部连通。Input 第一行输入两个正整数m和n,以下若干行每行四个正整数x1,y1,x2,y2,表示第x1行第y1列的点和第x2行第y2列的点已经有连线。输入... -
AcWing 1144. 连接格点(最小生成树)
2019-11-15 19:52:09某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有的点全部连通。 输入格式 第一行输入两个正整数 m 和 n。 以下若干行每行四个正整数 x1,y1,x2,y2,表示第 x1 行第 y1 列的点和第 x2 行第 y2 列的点... -
Fzoj1616连接格点
2016-08-18 11:27:54Fzoj1616连接格点 ... 题目描述 有一个M行N列的点阵,相邻两点可以相连。...某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有的点全部连通? 输入 第1行:输入两个正整数m和n。 以下若干行 -
最小生成树----------连接格点
2020-04-09 14:52:53某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有的点全部连通。输入格式第一行输入两个正整数 mm 和 nn 。以下若干行每行四个正整数 x1,y1,x2,y2x1,y1,x2,y2 ,表示第 x1x1 行第 y1y1 列的点和第 ... -
最小生成树 tyvj 连接格点grid
2017-09-02 11:20:50某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有的点全部连通。 输入格式 第一行输入两个正整数m和n。 以下若干行每行四个正整数x1,y1,x2,y2,表示第x1行第y1列的点和... -
连接格点(信息学奥赛一本通-T1394)
2018-06-30 00:23:01某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有的点全部连通。 【输入】 第一行输入两个正整数m和n。 以下若干行每行四个正整数x1,y1,x2,y2,表示第x1行第y1列的点和第x2行第y2列的点已经有... -
ssl2348-连接格点【图论,最小生成树,并查集】
2018-01-12 19:32:00某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有的点全部连通。 输入 第一行输入两个正整数m和n。 以下若干行每行四个正整数x1,y1,x2,y2,表示第x1行第y1列的点和第x2行第y2列的点已经有连线。... -
连接格点 解题报告
2015-08-11 16:53:52连接格点 时间限制: 1 Sec 内存限制: 128 MB ...某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有的点全部连通。 输入 第一行输入两个正整数m和n。(0 以下若干行每行四个正整数x1,y1,x -
第三部分 数据结构 --第四章 图论算法1394:连接格点(grid)
2020-05-27 08:19:43某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有的点全部连通。 【输入】 第一行输入两个正整数m和n。 以下若干行每行四个正整数x1,y1,x2,y2,表示第x1行第y1列的点和第x2行第y2列的点已经有连线。... -
【tyvj3303】连接格点,区分多维与单维很关键
2015-10-05 16:43:20连接格点(最小生成树) 时间: 1000ms / 空间: 65536KiB / Java类名: Main ...某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有的点全部连通。 输入格式 第一行输入两个正整数m和n。 -
(ssl 2348)连接格点#kruskal,并查集#
2018-01-06 14:28:19某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有的点全部连通。 分析:容我解释测试点 所以,既然求最小生成树,纵向优先。 那怎样连呢。 Kruskal 首先一... -
连接格点--------------------------图论(最小生成树)
2020-02-21 14:58:13某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有的点全部连通。 输入格式 第一行输入两个正整数 m 和 n。 以下若干行每行四个正整数 x1,y1,x2,y2,表示第 x1 行第 y1 列的点和第 x2 行第 y2 列的点... -
训练题 连接格点(并查集运用) 解题报告
2016-07-16 11:40:40某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有的点全部连通。 【输入格式】 第一行输入两个正整数m和n。 以下若干行每行四个正整数x1,y1,x2,y2,表示第x1行第y1
-
laravel 导出excel 一分钟解决
-
基于ARIMA-BP神经网络的CPU利用率预测模型研究
-
数据结构:逆波兰表达式问题(计算后缀表达式)
-
使用Rancher在Kubernetes上进行微服务部署
-
【布道者】Linux极速入门
-
电商PC前后端分离项目Spring Boot后台实战第一期
-
Galera 高可用 MySQL 集群(PXC v5.7+Hapro)
-
Android 权限申请案例以及注意事项
-
C3 AI全面增强其企业AI应用程序开发平台和AI应用程序
-
虚幻4引擎基础
-
iOSApp签名的原理
-
Galera 高可用 MySQL 集群(PXC v5.6 + Ngin
-
聊聊GitLab 持续集成发展历程
-
git的常用命令
-
微信小程序一:
-
基于Qt的LibVLC开发教程
-
Frog:具有混合着色模型的GPU上的异步图处理
-
MySQL 高可用工具 heartbeat 实战部署详解
-
乳胶型超高斯软边光阑
-
PPTP_NNN 服务生产环境实战教程