空间换取时间QWQ
直接暴力连边,然后跑Kru。
因为Kru一般都要排序,所以如果按我的方法再sort的话,就只能过掉前3个点,其他的都要超时。
这时候,我就发现,他只有1和2两种边权,所以完全没有排序的必要,我们用两个结构体来存储,一个存储边权为1的,一个存储边权为2的,然后就可以过掉,QWQ
参考代码
#pragma GCC target("avx","sse4","sse4.1","sse4.2","ssse3")
#pragma GCC target("f16c")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,m,sum,maxx;
int ans;
int sum2;
int pre[N];
bool vis[N];
int X1,X2,Y1,Y2;
struct Kruskal{
int x,y,z;
}kru[N*4],kru2[N*4];
inline int find(int i){
if(i==pre[i])
return i;
return pre[i]=find(pre[i]);
}
inline bool cmp(Kruskal a,Kruskal b){
return a.z<b.z;
}
int main(){
scanf("%d%d",&n,&m);
int l=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
l++;
pre[l]=l;
}
while(~scanf("%d%d%d%d",&X1,&Y1,&X2,&Y2)){
int l1=find((X1-1)*m+Y1);
int l2=find((X2-1)*m+Y2);
pre[l1]=l2;
}
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j){
if(i-1>=1){
int ls=(i-2)*m+j;
if(find(ls)==find((i-1)*m+j))
continue;
kru[++sum].x=(i-1)*m+j;
kru[sum].y=ls;
kru[sum].z=1;
}
if(j-1>=1){
int lz=(i-1)*m+j-1;
if(find(lz)==find((i-1)*m+j))
continue;
kru2[++sum2].x=(i-1)*m+j;
kru2[sum2].y=lz;
kru2[sum2].z=2;
}
if(i+1<=n){
int lx=i*m+j;
if(find(lx)==find((i-1)*m+j))
continue;
kru[++sum].x=(i-1)*m+j;
kru[sum].y=lx;
kru[sum].z=1;
}
if(j+1<=m){
int ly=(i-1)*m+j+1;
if(find(ly)==find((i-1)*m+j))
continue;
kru2[++sum2].x=(i-1)*m+j;
kru2[sum2].y=ly;
kru2[sum2].z=2;
}
}
//sort(kru+1,kru+1+sum,cmp);
for(int i=1;i<=sum;++i){
int xx=find(kru[i].x);
int yy=find(kru[i].y);
if(xx==yy)
continue;
pre[xx]=yy;
ans+=kru[i].z;
}
for(int i=1;i<=sum2;++i){
int xx=find(kru2[i].x);
int yy=find(kru2[i].y);
if(xx==yy)
continue;
pre[xx]=yy;
ans+=kru2[i].z;
}
printf("%d",ans);
}