题解：P11224 [COTS 2019] 挑战 Izazov

andychen_2012 · 2024-11-10 10:46:51 · 题解

这原来竟是一道论文题，确实较难。

论文链接：Graph-Theoretic Solutions to Computational Geometry Problems。

我们一步步来吧。

首先我们有一个非常直接的想法，将所有横着的连续段划分成一个矩形，或将所有竖着的连续段划分成一个矩形，这样子可以获得 30pts 的好成绩。

接下来我们考虑合并两个相邻的大小相同的矩形，进行完合并后，可以得到 38pts 的好成绩。

为啥这不对呢？主要是因为有些可以合并的矩形因为合并后会将原有的一个矩形切割开，因此就没有去合并。应该如何去找到这些需要去合并的矩形呢？

到这里之后卡住了，那不如我们来思考一下最终的最小覆盖数如何计算好了。

我们认为一个连通块是一个多边形，多边形中可能存在一些洞，如下图 1。

我们注意到一个矩形有四个角，那么我们切分出来的矩形数 \times 4 应该不少于原来多边形的顶点数。

那么切分后多出来的顶点数由什么贡献呢？由凹顶点所在的边与原多边形上的边（或另一个划分出的矩形的边）相交而贡献。但是假如矩形的某条边的端点是两个凹顶点，则不会贡献出新的顶点。

那么我们有这样的结论：

定义好对角线为输入多边形内部连接多边形两个凹顶点的轴平行线段。具有 n 个顶点和 h 个洞的多边形中划分出的矩形的最小数量为 \frac{n}{2}+h-g-1，其中 g 是一组不相交的好对角线的最大大小。

证明：

设 G 是构成多边形由不相交的好对角线所构成的的最大集合，并将坏顶点定义为不是 G 中任意一条对角线端点的非凸多边形顶点。每个多边形顶点至少贡献一个矩形的顶点。
对于每个坏顶点 v，令 s 表示一条以 v 为端点的线段。则 s 有如下两种情况：
由这两种情况可以得到，一个划分中，矩形角的数量至少为 n+ 2 |v|，其中 |v| 表示坏顶点的数量。
在任何有 h 个洞的多边形中，非凸顶点的数量是 n/2+2h-2，因此坏顶点的数量为 n/2+2h-2|G|-2，并且遵循 n/2+h-|G|-1 个矩形的下限。
相反，如果 G 是任何一组不相交的好对角线，那么通过依次考虑 G 的坏顶点，并将一条线段从每个坏顶点延伸到最近的先前添加的线段或多边形边，可以找到一个正好有 n/2+h-|G|-1 个矩形的划分方案。因此，将一个多边形划分为最小数量的矩形相当于找到最大数量的不相交好对角线。

好对角线的交集图是二分的：每个水平对角线只与垂直对角线相交，反之亦然。因此，在图论中，找到不相交好对角线的最大数量转化为在二分图中找到最大独立集。根据 \text{K\"onig} 定理，在任何 n-顶点二分图中，最大独立集的大小为 n-M，其中 M 是最大匹配的数量。

我们注意到两条对角线最多交于一点，一个点最多被两条对角线经过。因此我们对每个点记录哪条对角线经过它，如果有两条对角线同时经过它，则在二分图上，这两条对角线有一条边。

可以直接写一个匈牙利跑二分图最大独立集，从上面可以看出边数和点数之积大小最大在 O(n^3)。

那么根据凹对角线划分完之后，我们得到所有划分出来的多边形都满足如下的性质：不存在凹对角线，这样子我们可以直接按合并算法做即可，每次合并两个相同大小的在同一个划分中的矩形。如下是样例 3 的多边形及其凹对角线划分，绿线即为最大的凹对角线连边集，蓝线为多边形的边：

图丑，见谅。

当然，如果想更快一些，可以使用网络流来做二分图最大独立集。下面的代码使用了网络流。

还有一个细节在如何找对角线，我的做法是寻找所有形如下面形状的位置：

BC  CB  CC  CC
CC  CC  BC  CB

凹顶点只在这些位置上出现，每次对于两个相邻凹顶点间连边即可，时间复杂度是 O(n^2) 的。注意一共有 8 种可能的相邻凹顶点图形，要讨论清楚。

#include<cstdio>
#include<vector>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
inline ll read(){
    ll x=0;
    int f=0,ch=0;
    while(ch<48||ch>57) f=(ch=='-'),ch=getchar();
    while(ch>47&&ch<58) x=(x<<3)+(x<<1)+(ch&15),ch=getchar();
    return f?-x:x;
}
inline void write(ll x,char end='\n'){
    if(x==0){
        putchar('0');
        putchar(end);
        return;
    }
    if(x<0) putchar('-'),x=-x;
    int ch[40]={0},cnt=0;
    while(x){
        ch[cnt++]=(int)(x%10);
        x/=10;
    }
    while(cnt--) putchar(ch[cnt]+48);
    putchar(end);
}
const int N=505;
int n,m;
char s[N][N];
int a[N][N],cnt;
int sum[N][N];
bool vis[N*N],bel[N][N][2];
int to[N*N];
int tot,left;
int bevis[N][N][2];
inline bool check(int a1,int a2,int b1,int b2,int c1,int c2){return s[a1][a2]=='C'&&s[b1][b2]=='C'&&s[c1][c2]=='B';}
inline void init(){
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+(s[i][j]=='C');
        }
    }
    for(int i=2;i<=n;++i){
        for(int j=1;j<=m;++j){
            if(s[i][j]=='B') continue;
            if(j>1&&check(i-1,j,i,j-1,i-1,j-1)){
                for(int k=i;k<n;++k){
                    if(s[k][j]=='B') break;
                    bool f1=check(k+1,j,k,j-1,k+1,j-1);
                    bool f2=check(k+1,j-1,k,j-1,k+1,j);
                    if(f1||f2){
                        ++tot;
                        for(int t=i;t<=k;++t) bevis[t][j][0]=tot;
                        break;
                    }
                }
            }
            if(j<m&&check(i-1,j,i,j+1,i-1,j+1)){
                for(int k=i;k<n;++k){
                    if(s[k][j]=='B') break;
                    bool f1=check(k+1,j,k,j+1,k+1,j+1);
                    bool f2=check(k+1,j+1,k,j+1,k+1,j);
                    if(f1||f2){
                        ++tot;
                        for(int t=i;t<=k;++t) bevis[t][j+1][0]=tot;
                        break;
                    }
                }
            }
        }
    }
    left=tot;
    for(int i=1;i<=n;++i){
        for(int j=2;j<=m;++j){
            if(s[i][j]=='B') continue;
            if(i>1&&check(i-1,j,i,j-1,i-1,j-1)){
                for(int k=j;k<m;++k){
                    if(s[i][k]=='B') break;
                    bool f1=check(i-1,k,i,k+1,i-1,k+1);
                    bool f2=check(i-1,k,i-1,k+1,i,k+1);
                    if(f1||f2){
                        ++tot;
                        for(int t=j;t<=k;++t) bevis[i][t][1]=tot;
                        break;
                    }
                }
            }
            if(i<n&&check(i+1,j,i,j-1,i+1,j-1)){
                for(int k=j;k<m;++k){
                    if(s[i][k]=='B') break;
                    bool f1=check(i+1,k,i,k+1,i+1,k+1);
                    bool f2=check(i+1,k,i+1,k+1,i,k+1);
                    if(f1||f2){
                        ++tot;
                        for(int t=j;t<=k;++t) bevis[i+1][t][1]=tot;
                        break;
                    }
                }
            }
        }
    }
}
struct node{
    int to,nxt,w;
}e[N*N<<2];
int head[N*N],ecnt=1;
inline void add(int u,int v,int w){
    e[++ecnt]={v,head[u],w};
    head[u]=ecnt;
}
const int inf=2e9;
int dis[N*N],now[N*N];
queue<int> q;
inline bool bfs(){
    while(!q.empty()) q.pop();
    for(int i=0;i<=tot+1;++i) dis[i]=inf;
    dis[0]=0;
    now[0]=head[0];
    q.push(0);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=now[u];i;i=e[i].nxt){
            int v=e[i].to;
            if(e[i].w>0&&dis[v]==inf){
                dis[v]=dis[u]+1;
                now[v]=head[v];
                if(v==tot+1) return 1;
                q.push(v);
            }
        }
    }
    return 0;
}
inline int dfs(int u,int sum){
    if(u==tot+1) return sum;
    int res=0;
    for(int i=now[u];i&&sum;i=e[i].nxt){
        now[u]=i;
        int v=e[i].to;
        if(e[i].w>0&&dis[v]==dis[u]+1){
            int d=dfs(v,min(sum,e[i].w));
            if(!d) dis[v]=inf;
            res+=d;sum-=d;
            e[i].w-=d;e[i^1].w+=d;
        }
    }
    return res;
}
inline void getmatching(){
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            if((bevis[i][j][0]||bevis[i-1][j][0])&&(bevis[i][j][1]||bevis[i][j-1][1])){
                int u=bevis[i][j][0]|bevis[i-1][j][0];
                int v=bevis[i][j][1]|bevis[i][j-1][1];
                add(u,v,1);add(v,u,0);
            }
        }
    }
    for(int i=1;i<=left;++i) add(0,i,1),add(i,0,0);
    for(int i=left+1;i<=tot;++i) add(i,tot+1,1),add(tot+1,i,0);
    while(bfs()) dfs(0,inf);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            if(bevis[i][j][0]&&dis[bevis[i][j][0]]!=inf) bel[i][j][0]=1;
            if(bevis[i][j][1]&&dis[bevis[i][j][1]]==inf) bel[i][j][1]=1;
        }
    }
}
inline void solve(){
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            if(s[i][j]=='B'||a[i][j]) continue;
            int r=j;
            for(int k=j+1;k<=m;++k){
                if(s[i][k]=='B'||bel[i][k][0]) break;
                r=k;
            }
            int plc=i;
            for(int k=i+1;k<=n;++k){
                if(bel[k][j][1]) break;
                if(sum[k][r]-sum[k][j-1]-sum[i-1][r]+sum[i-1][j-1]!=(r-j+1)*(k-i+1)) break;
                if(j>1&&(s[k][j-1]=='C'&&(!a[k][j-1])&&(!bel[k][j][0]))) break;
                if(r<m&&(s[k][r+1]=='C'&&(!a[k][r+1])&&(!bel[k][r+1][0]))) break;
                plc=k;
            }
            ++cnt;
            for(int k=i;k<=plc;++k){
                for(int t=j;t<=r;++t)
                    a[k][t]=cnt;
            }
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j)
            vis[a[i][j]]=1;
    }
    int ncnt=0;
    for(int i=1,now=1;i<=cnt;++i){
        if(vis[i]) to[i]=now++,++ncnt;
    }
    cnt=ncnt;
}
int main(){
//  freopen("input.txt","r",stdin);
//  freopen("1.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=n;++i)
        scanf("%s",s[i]+1);
    init();
    getmatching();
    solve();
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j)
            write(a[i][j],j==m?'\n':' ');
    }
    return 0;
}