P6171 题解

Mu_tr · 2022-01-24 11:47:51 · 题解

题目大意

给一个大矩形，中间有一些横线和竖线，这些线又将整个大矩形分成 (n+1)\cdot(m+1) 个小矩形，问最少删掉多长的线段可以让这些小矩形连通。

题目思路

很明显我们可以将这道题抽象成一道最小生成树问题，将一个小矩形看成一个点，然后将这个小矩形和四个方向上的其他矩形连边，由于小矩形的个数最多为 2001\times 2001=4004001，那么总边数即为 4004001\times 4=16016004，由于这道题中的边是无向边，所以我们一条边会被连两次，删掉重复的那么总边数即为 16016004\div 2=8008002 。这里我们采用的是 kruskal 算法，时间复杂度还需要带上一个并查集的，代码中我使用了启发式合并和路径压缩两种优化方式优化时间复杂度，所以总时间复杂度为 O(nm\alpha(nm)) ，\alpha(nm) 可以看做一个小于 5 的常数，所以总运行次数即为 10^8 左右。在本机上不吸氧最后一个测试点用时 1.7s 左右，但洛谷会超时，不过吸口氧还是能够轻松过的，最后一个测试点只用了 0.7s。

AC代码

#include<bits/stdc++.h>
using namespace std;
int cnt=0,n,m,a,b,x[2005],y[2005],f[4010005],rt[4010005],q1,q2,p;
long long ans1=0;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
struct ok{
    int ans,w1,w2;
}q[8020005];
inline bool cmp(ok x,ok y){
    return x.ans<y.ans;
}
inline int find(int k){
    return k==f[k]?k:f[k]=find(f[k]);
}
inline int js(int x,int y){
    return x*(m+1)+y+1;
}
signed main(){ 
    a=read(),b=read(),n=read(),m=read();
    for(register int i=1;i<=n;i++) x[i]=read();
    for(register int i=1;i<=m;i++) y[i]=read();
    sort(x+1,x+1+n);sort(y+1,y+1+m);
    x[n+1]=a;y[m+1]=b;
    for(register int i=0;i<=n;i++){
        for(register int j=0;j<=m;j++){
            p=js(i,j);
            f[p]=p;rt[p]=1;
            if(j!=m) q[++cnt].ans=x[i+1]-x[i],q[cnt].w1=p,q[cnt].w2=p+1;
            if(i!=n) q[++cnt].ans=y[j+1]-y[j],q[cnt].w1=p,q[cnt].w2=p+m+1;
        }
    }
    sort(q+1,q+1+cnt,cmp);
    for(register int i=1;i<=cnt;i++){
        q1=find(q[i].w1),q2=find(q[i].w2);
        if(q1!=q2){
            rt[q1]>rt[q2]?(f[q2]=f[q1],rt[q1]+=rt[q2]):(f[q1]=f[q2],rt[q2]+=rt[q1]);
            ans1+=q[i].ans;
        }   
    }
    printf("%lld",ans1); 
    return 0;
}