题解 CF1416F Showing Off

tzc_wk · 2023-05-04 12:17:42 · 题解

昨天难得模拟赛没有流，所以开道流玩玩（

首先这个连边关系显然形成一个基环树。考虑什么样的点会在环上。发现两个性质：

同一个环上的点的 a 都相同。
如果一个点四周没有 a 比它小的点，那么这个点必须在某个环上，否则它可能在某个环上，也可能不在。

我们记 vis_{i,j} 表示其是否一定在某个环上，然后考虑用流求出一种合法的安排环的方案。对于这种“n\times m 的网格，每个点有唯一后继，要求成环”的网络流问题，我们有一般有两种建模方式：

类似于最小路径覆盖，将每个点的入边看作上部点，将每个点的出边看作下部点，然后跑二分图匹配，但是对于这题而言，不可做的地方在于没法限制一个点如果上部点在匹配中，下部点也一定在匹配中，因此舍弃这个想法。
类似于清华集训 2017 无限之环，将矩阵黑白染色，黑点看作上部点，白点看作右部点，然后还是跑二分图匹配。发现这个想法是可行的。

这样建模思路就出来了，对于一个黑点 (i,j)，连边 S\to (i,j)，下界 vis_{i,j}，上界 1，对于白点则想 T 连，对于一个黑点 (i,j) 及其邻居 (x,y)，如果 a_{i,j}=a_{x,y}，从 (i,j) 向 (x,y) 连边，下界 0 上界 1，然后跑有源汇可行流即可。如果不存在可行流答案就是 NO，否则考虑每条匹配边，我们强制令其形成大小为 2 的环，一个填 1 一个填 a_{i,j}-1，因为对于任意一种染色方案，我们必然可以调整其使其只包含大小为 2 的环（证明还是考虑黑白染色，挺 trivial 的），因此我们的构造是 ok 的。

接着考虑不在环上的点，显然，因为相邻的四个点中存在一个 a 比它小的点，因此我们只用令其指向那个点，然后矩阵中填的数为二者的 a 之差即可。

时间复杂度 nm\sqrt{nm}。

const int MAXN=1e5;
const int dx[]={1,0,-1,0};
const int dy[]={0,1,0,-1};
const char str[]="DRUL";
const int INF=0x3f3f3f3f;
int n,m,a[MAXN+5],b[MAXN+5],vis[MAXN+5];char c[MAXN+5];
int getid(int x,int y){return (x-1)*m+y;}
namespace MaxFlow{
    const int MAXV=1e5+4;
    const int MAXE=1e6;
    int S,T,SS,TT,hd[MAXV+5],to[MAXE+5],nxt[MAXE+5],cap[MAXE+5],ec=1;
    void adde(int u,int v,int f){
        to[++ec]=v;cap[ec]=f;nxt[ec]=hd[u];hd[u]=ec;
        to[++ec]=u;cap[ec]=0;nxt[ec]=hd[v];hd[v]=ec;
    }
    void adde(int u,int v,int l,int r){
        if(!l)adde(u,v,r);
        else adde(SS,v,l),adde(u,TT,l);
    }
    void clear(){for(int i=1;i<=TT;i++)hd[i]=0;ec=1;}
    int dep[MAXV+5],now[MAXV+5];
    bool getdep(){
        for(int i=1;i<=TT;i++)dep[i]=-1;
        queue<int>q;q.push(SS);dep[SS]=0;
        while(!q.empty()){
            int x=q.front();q.pop();now[x]=hd[x];
            for(int e=hd[x];e;e=nxt[e]){
                int y=to[e],z=cap[e];
                if(z&&!~dep[y]){dep[y]=dep[x]+1;q.push(y);}
            }
        }return ~dep[TT];
    }
    int getflow(int x,int f){
        if(x==TT)return f;int ret=0;
        for(int &e=now[x];e;e=nxt[e]){
            int y=to[e],z=cap[e];
            if(z&&dep[y]==dep[x]+1){
                int w=getflow(y,min(f-ret,z));
                cap[e]-=w;cap[e^1]+=w;ret+=w;
                if(ret==f)return ret;
            }
        }return ret;
    }
    int dinic(){int ret=0;while(getdep())ret+=getflow(SS,INF);return ret;}
}using namespace MaxFlow;
void solve(){
    scanf("%d%d",&n,&m);S=n*m+1;T=n*m+2;SS=n*m+3;TT=n*m+4;
    for(int i=1;i<=n*m;i++)vis[i]=b[i]=0;clear();
    for(int i=1;i<=n*m;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
        bool flg=0;
        for(int d=0;d<4;d++){
            int x=i+dx[d],y=j+dy[d];
            if(x<1||x>n||y<1||y>m)continue;
            flg|=(a[getid(x,y)]<a[getid(i,j)]);
        }
        vis[getid(i,j)]=flg^1;
    }
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
        if((i+j)&1)adde(S,getid(i,j),vis[getid(i,j)],1);
        else adde(getid(i,j),T,vis[getid(i,j)],1);
        if((i+j)&1){
            for(int d=0;d<4;d++){
                int x=i+dx[d],y=j+dy[d];
                if(x<1||x>n||y<1||y>m)continue;
                if(a[getid(x,y)]==a[getid(i,j)])adde(getid(i,j),getid(x,y),1);
            }
        }
    }
    adde(T,S,INF);int nd=0;
    for(int i=1;i<=n*m;i++)nd+=vis[i];
    if(dinic()!=nd)return puts("NO"),void();
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if((i+j)&1){
        for(int e=hd[getid(i,j)];e;e=nxt[e]){
            int y=to[e];
            if(y!=S&&cap[e^1]){
                b[getid(i,j)]=1;b[y]=a[y]-1;
                for(int d=0;d<4;d++){
                    int X=i+dx[d],Y=j+dy[d];
                    if(X<1||X>n||Y<1||Y>m)continue;
                    if(getid(X,Y)==y)c[getid(i,j)]=str[d],c[y]=str[d^2];
                }
            }
        }
    }
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(!b[getid(i,j)]){
        for(int d=0;d<4;d++){
            int x=i+dx[d],y=j+dy[d];
            if(x<1||x>n||y<1||y>m)continue;
            if(a[getid(x,y)]<a[getid(i,j)]){
                b[getid(i,j)]=a[getid(i,j)]-a[getid(x,y)];
                c[getid(i,j)]=str[d];break;
            }
        }
    }
    puts("YES");
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
        printf("%d%c",b[getid(i,j)]," \n"[j==m]);
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
        printf("%c%c",c[getid(i,j)]," \n"[j==m]);
}
int main(){
    int qu;scanf("%d",&qu);while(qu--)solve();
    return 0;
}
/*
1
4 4
7 6 7 8
5 5 4 4
5 7 4 4
5 10 10 10
*/