当前位置: 首页> 教育> 大学 > 快速建站套餐_长春营销型网站制作_网络公司优化关键词_婚恋网站排名前三

快速建站套餐_长春营销型网站制作_网络公司优化关键词_婚恋网站排名前三

时间:2025/7/10 10:19:41来源:https://blog.csdn.net/lq1990717/article/details/143457433 浏览次数:0次
快速建站套餐_长春营销型网站制作_网络公司优化关键词_婚恋网站排名前三

【题目链接】

ybt 1394:连接格点(grid)

【题目考点】

1. 图论:最小生成树

【解题思路】

该题和ybt 1393:联络员(liaison)考察内容是相同的。
每个点是一个图中顶点,相邻点可以连线。
题目中给的是坐标,我们需要把坐标数对和表示顶点编号的整数对建立映射关系,这样就可以通过坐标取到对应的顶点。
将题目中的x、y都减1,坐标就成了从0开始的数对。我们希望坐标和顶点编号有进行这样的对应关系
(0,0)–0, (0,1)–1, (0,2)–2, …, (0,n-1)–n-1
(1,0)–n, (1,1)–n+1, (1,2)–n+2, …, (1,n-1)–2n-1
(2,0)–2n, (2,1)–2n+1, (2,2)–2n+2, …, (2,n-1)–3n-1

(m-1, 0)–(m-1)n, (m-1, 1)–(m-1)n+1, …, (m-1, n-1)–mn-1
观察规律可知,坐标 ( x , y ) (x, y) (x,y)对应的顶点编号为 x n + y xn+y xn+y
每个点和其上下左右点都可以连线,相邻点之间当做有一条边,纵向的边权值为1,横向的边权值为2,建图。
在图中先选择已连线的边,也就是将已连接的边所连接的两个顶点所在集合合并。而后执行Kruskal算法,不断选择权值最小的边,如果该边两端的顶点不在同一集合(连通分量)中,就将两顶点所在集合合并。(如果当前权值最小的边是已连线的边,那么该边的两个顶点一定已经在同一集合中,不会进行再次合并。)选出的边和已有的边会构成一个权值加和最小的连通图,其原理见ybt 1393:联络员(liaison)。
行数、列数最大为 1 0 3 10^3 103,顶点数量最大会达到 1 0 6 10^6 106,每个顶点向右、向下连接一条边,连出的边数和图中的总边数接近,因此边数最大大约会达到 2 ∗ 1 0 6 2*10^6 2106个。Kruskal算法的复杂度为 O ( E l o g E ) O(ElogE) O(ElogE),当E为 2 ∗ 1 0 6 2*10^6 2106时,算法运行总时间小于1s,可以通过。

【题解代码】

解法1:Kruskal算法
#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;
}
关键字:快速建站套餐_长春营销型网站制作_网络公司优化关键词_婚恋网站排名前三

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: