网格图先黑白染色,由于格子无法向边界外连边,且为正数,所以最后一定是一个基环树森林,并且一定是偶环,那么就可以把一个环拆分成多个二元环,更加方便;每个格子前往的点一定比它自己小,所以一个格子周围的数都比它大,那么无解,如果等于,那么就在同一个环上,否则一定会先经过一些树边,然后到达一个环;由于黑白染了色,且每个环为两个部分,所以考虑二分图。
现在我们就可拿出环上的点让它们两两匹配;如果它可以不在环上,也就是四联通内有小于它的点,那么它就可匹配也可不匹配,那么它与源点(汇点)的连边下界为 \(0\),上界为 \(1\),否则上下界均为 \(1\);如果两点可以在一个环上,那么两点连接下界 \(0\),上界 \(1\) 的边,最后跑一个有汇源有上下界可行流即可。
#include<bits/stdc++.h>
using namespace std;
int k,n,m,s,t,S,T,tot=1,flow,maxflow,allflow,a[100001],w[100001],head[110001],now[110001],dep[110001],nex[3000001],edge[3000001],ver[3000001],dx[5]={0,0,1,-1},dy[5]={1,-1,0,0};
char b[100001],dz[5]={'R','L','D','U'};
queue <int> q;
#define id(i,j) ((i-1)*m+j)
void add(int u,int v,int w){
ver[++tot]=v,edge[tot]=w,nex[tot]=head[u],head[u]=tot;
ver[++tot]=u,edge[tot]=0,nex[tot]=head[v],head[v]=tot;
}
bool bfs(){
memset(dep,0,sizeof(dep));
while(q.size()) q.pop();
q.push(s);
dep[s]=1;
while(q.size()){
int x=q.front();
q.pop();
for(int i=head[x];i;i=nex[i]){
if(edge[i]&&!dep[ver[i]]){
q.push(ver[i]);
dep[ver[i]]=dep[x]+1;
if(ver[i]==t) return true;
}
}
}
return false;
}
int dinic(int x,int flow){
if(x==t) return flow;
int rest=flow,k;
for(int i=now[x];i&&rest;i=nex[i]){
now[x]=i;
if(edge[i]&&dep[ver[i]]==dep[x]+1){
k=dinic(ver[i],min(edge[i],rest));
if(!k) dep[ver[i]]=0;
rest-=k;
edge[i]-=k;
edge[i^1]+=k;
}
}
return flow-rest;
}
void solve(){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int F=0;
for(int d=0;d<=3;d++){
int x=i+dx[d],y=j+dy[d];
if(x<1||y<1||x>n||y>m) continue;
F|=(w[id(i,j)]>w[id(x,y)]);
if(w[id(i,j)]>w[id(x,y)]){
a[id(i,j)]=w[id(i,j)]-w[id(x,y)];
b[id(i,j)]=dz[d];
}
else if(w[id(i,j)]==w[id(x,y)]&&((i+j)&1)) add(id(i,j),id(x,y),1);
}
if((i+j)&1){
if(!F) allflow++,add(s,id(i,j),1),add(S,t,1);
else add(S,id(i,j),1);
}
else{
if(!F) allflow++,add(s,T,1),add(id(i,j),t,1);
else add(id(i,j),T,1);
}
}
}
add(T,S,1e9);
while(bfs()){
for(int i=s;i<=t;i++) now[i]=head[i];
while(flow=dinic(s,1e9)) maxflow+=flow;
}
if(maxflow!=allflow){
printf("NO\n");
return;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(!((i+j)&1)) continue;
for(int l=head[id(i,j)];l;l=nex[l]){
if(ver[l]>=1&&ver[l]<=n*m&&!edge[l]){
a[id(i,j)]=1;
a[ver[l]]=w[id(i,j)]-1;
if(j<m&&ver[l]==id(i,j+1)){
b[id(i,j)]=dz[0];
b[ver[l]]=dz[1];
}
if(j>1&&ver[l]==id(i,j-1)){
b[id(i,j)]=dz[1];
b[ver[l]]=dz[0];
}
if(i<n&&ver[l]==id(i+1,j)){
b[id(i,j)]=dz[2];
b[ver[l]]=dz[3];
}
if(i>1&&ver[l]==id(i-1,j)){
b[id(i,j)]=dz[3];
b[ver[l]]=dz[2];
}
break;
}
}
}
}
printf("YES\n");
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++) printf("%d ",a[id(i,j)]);
printf("\n");
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++) printf("%c ",b[id(i,j)]);
printf("\n");
}
}
int main(){
scanf("%d",&k);
while((k--)&&(tot=1)&&!(maxflow=allflow=0)){
scanf("%d%d",&n,&m);
S=n*m+1,T=n*m+2,t=n*m+3;
memset(head,0,sizeof(head));
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&w[id(i,j)]);
solve();
}
return 0;
}
标签:ver,int,Showing,CF1416F,dep,add,tot,Off,id
From: https://www.cnblogs.com/zyxawa/p/18328043