自己yy的算法
自己yy一波....
我们其实可以将每一个点看做一个数.
然后再用类似求最小生成树的方法分别从横向和纵向分别依次合并相邻两点.
如果当前相邻的两点没有连接,就将其合并,边合并边记录答案.
(注意下文中的坐标均指在C++二维数组表示下的坐标)
接下来说一下将坐标转化为数字,其实就相当于给每一个坐标一个编号,那么
我们就将每一个坐标通过一个特定的规则转换为其对应的编号.
具体怎么做,
在此举一个例子:(以n=3,m=5为例)
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
通过这个矩阵,我们顺利的将每一个坐标编上了序号.
例如:坐标(1,1)的编号为1,坐标(1,2)的编号为2,
坐标(2,2)的编号为7,坐标(2,1)的编号为6,以此类推.
容易看出:如果当前的坐标为(x,y),那么他对应的编号就是(x-1)*m+y.
解决了这个问题,剩下的简直就是小儿科了…
时间复杂度 应该是$O(nlogn)$吧....
C++ 代码
#include<bits/stdc++.h>
#define N 1010
using namespace std;
int n,m;
int fa[N*N],tot;
int find(int x)//并查集基本操作
{
if(fa[x]==x)
return x;
return fa[x]=find(fa[x]);
}
inline int merge(int x,int y)//并查集基本操作
{
int fa_x=find(x);
int fa_y=find(y);
if(fa_x!=fa_y){
fa[fa_y]=fa_x;
return 1;//已经连了一条边
}
return 0;
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n*m;i++)//并查集初始化
fa[i]=i;
int x1,y1,x2,y2;
while(~scanf("%d %d %d %d",&x1,&y1,&x2,&y2)){
int u=(x1-1)*m+y1,v=(x2-1)*m+y2;//转换为对应的编号
merge(u,v);//合并
}
for(int i=1;i<=m;i++)//竖向合并一遍
for(int j=1;j<n;j++){
int u=(j-1)*m+i,v=j*m+i;//坐标转换
if(merge(u,v))//当前两点有一条边连接
tot++;//竖向答案+1
}
for(int i=1;i<=n;i++)//横向合并一遍
for(int j=1;j<m;j++){
int u=(i-1)*m+j,v=(i-1)*m+j+1;//坐标转换
if(merge(u,v))//当前两点有一条边连接
tot+=2;//横向答案+2
}
printf("%d\n",tot);
return 0;
}
改了下大佬的合并过程 这样感觉思维量更少一点
记录美好生活
感谢大佬,我那个转化一维坐标一直没懂,看了你的解释懂了orz
while输入中“ ~ ”为什么那么神奇啊,有大神解说一下吗(萌新求打)
如果scanf没有读入返回值-1,(~)这个符号就是二进制取反操作,-1取反后就变成0就退出while循环了
yy
这不是<<一本通>>里的标程吗
复杂度O(nmlogn)…
合并操作不用logn
并查集查询复杂度趋近于O(1)的,有路径压缩优化,当然nmlogn应该也能过,复杂度O(10^7)
yy是啥意思?
巧了,我也是这么yy的
复杂度不是O(nm)吗
是的,并查集带路径压缩近似看成常数。