首页 > 其他分享 >CF1416F Showing Off

CF1416F Showing Off

时间:2024-07-28 11:52:51浏览次数:14  
标签:ver int Showing CF1416F dep add tot Off id

网格图先黑白染色,由于格子无法向边界外连边,且为正数,所以最后一定是一个基环树森林,并且一定是偶环,那么就可以把一个环拆分成多个二元环,更加方便;每个格子前往的点一定比它自己小,所以一个格子周围的数都比它大,那么无解,如果等于,那么就在同一个环上,否则一定会先经过一些树边,然后到达一个环;由于黑白染了色,且每个环为两个部分,所以考虑二分图。

现在我们就可拿出环上的点让它们两两匹配;如果它可以不在环上,也就是四联通内有小于它的点,那么它就可匹配也可不匹配,那么它与源点(汇点)的连边下界为 \(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

相关文章

  • dpdk下ipsec内联卸载(inline offload)测试
    使用intel82599网卡完成。介绍本文介绍了数据平面开发套件(DPDK)框架中的内联IPsec加速支持实现,特别关注英特尔®8259910千兆以太网控制器系列的功能和支持。内联IPsec可用于实现IPsec感知系统,该系统具有比旁路辅助和加速硬件更好的延迟,前提是支持的算法合适。......
  • 国产linux系统(银河麒麟,统信uos)使用 PageOffice 国产版实现Word多文件合并
    国产linux系统(银河麒麟,统信uos)使用PageOffice国产版在线打开pdf文件PageOffice国产版:支持信创系统,支持银河麒麟V10和统信UOS,支持X86(intel、兆芯、海光等)、ARM(飞腾、鲲鹏、麒麟等)芯片架构。本示例关键代码的编写位置Vue+Springboot注意本文中展示的代码均为关键代码,复......
  • 数据结构与算法,剑指Offer 50题
    队列队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。对列的添加insertappend队列的取值列表[-1]列表[0]队列的删......
  • 自编译制作docker版本的onlyoffice镜像
    笔记记录自编译制作docker版本的onlyoffice镜像一、环境:1、win11安装Ubuntu20.04.6.LTS2、需要开代理文件参考:https://helpcenter.onlyoffice.com/installation/docs-community-compile.aspx二、准备1、sudoapt-getupdate2、sudoapt-getinstall-ygitpythonopenssh-......
  • 使用微软自己的方法,将Office文档转化为pdf
    转的,整理资料发现的,挺好。原创作者找不到了。//////Word转换成pdf//////源文件路径///目标文件路径///true=转换成功publicboolDOCConvertToPDF(stringsourcePath,stringtargetPath){boolresult=false;Word.WdExportFormatexportFormat=Word.WdExport......
  • office365.sharepoint 中的 moveto 或 move_to_using_path 是否处于活动状态?
    我正在尝试使用Office365-REST-Python-Client中的示例将文件从一个文件夹移动到另一个文件夹,但它不起作用:fromoffice365.sharepoint.client_contextimportClientContextfromoffice365.sharepoint.files.move_operationsimportMoveOperationsfromtestsimporttest_t......
  • 使用onlyoffice完成Word、Excel、PowerPoint 文件在线预览、编辑、保存功能
    环境准备64-bitWindowsServer2012orhigher我自己使用的服务器配置是2核2G,带宽是2M,也就是说高于这个配置的服务器都是没有问题的。大家在挑选的时候,如果只是用来作为onlyoffice的文档服务器来使用,那么配置可以低一些,带宽越大越好安装步骤将上面的安装包全部下载到本地服......
  • 将 Met Office 数据点 JSON 读入 Panda
    我正在使用MetOfficeDatapointAPI下载JSON格式的英国天气数据。然后我想将该JSON文件读入pandasDataFrame。JSON文件的格式如图所示{"SiteRep":{"Wx":{"Param":[{"name":"FDm","units":"C","$":"FeelsLikeDa......
  • 国产linux系统(银河麒麟,统信uos)使用 PageOffice 国产版在线打开 word文件自定义模板中
    国产linux系统(银河麒麟,统信uos)使用PageOffice国产版在线打开pdf文件PageOffice国产版:支持信创系统,支持银河麒麟V10和统信UOS,支持X86(intel、兆芯、海光等)、ARM(飞腾、鲲鹏、麒麟等)芯片架构。本示例关键代码的编写位置Vue+Springboot注意本文中展示的代码均为关键代码,复......
  • 大专学历,快 30 岁,裁员 2 个月,拿到 25k+ 的 Offer,优秀!!.md
    大家好,我是R哥。最近做面试辅导,帮到了太多小伙伴入职了,大多都是统招「二本」及以上学历,其实也有好几个「大专」、「专升本」学历辅导入职的案例。比如我今天要分享的这个激动人心的面试辅导成功案例,这兄弟我管他叫「小王」好了,小王他就是大专学员:小王也算是我的铁粉,在裁员一周......