正解:网络流

解题报告:

传送门!

日常看不懂题系列,,,$QAQ$

所以先放下题目大意趴$QwQ$,就说有个$p\cdot q$的矩阵,每个位置可以填一个$[1,R]$范围内的整数$a_{i,j}$,要求相邻格子之间差不超过$D$.求$\sum v_{i,j,a_{i,j}}$的$min$

昂,先考虑如果没有$D$这个限制网络流怎么做鸭$QwQ$.就一个,比较显然的最小割,对每个位置$(i,j)$开一行点连起来,第$k$个点和第$k+1$个点之间的流量为$v_{i,j,k+1}$,切开就表示这个位置取值为$k+1$,跑个最小割就好$QwQ$

然后现在加上了一个,相差不能超过$D$的约束,考虑怎么加边保证相差不超过$D$?$QwQ$

昂懒得写过程了直接说结论趴,就连接每对$(i,j,k)$&$(i\pm 1,j\pm 1,k-D)$,就可以保证如果选的是两个差距大于$D$的数时不可能是满流$QwQ$

最后跑个最小割就成,$over$

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define gc getchar()
#define t(i) edge[i].to
#define n(i) edge[i].nxt
#define w(i) edge[i].wei
#define ri register int
#define rb register bool
#define rc register char
#define rp(i,x,y) for(ri i=x;i<=y;++i)
#define e(i,x) for(ri i=head[x];~i;i=n(i)) const int N=+,inf=1e9;
int S,T,ed_cnt=-,head[N],as,cur[N],dep[N],p,q,r,d;
int mov_x[]={,,,-},mov_y[]={,-,,};
struct ed{int to,nxt,wei;}edge[N<<]; il int read()
{
rc ch=gc;ri x=;rb y=;
while(ch!='-' && (ch>'' || ch<''))ch=gc;
if(ch=='-')ch=gc,y=;
while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;
return y?x:-x;
}
il int nam(ri x,ri y,ri z){return ((x-)*q+y-)*r+z;}
il void print(ri dat)
{
if(!dat)return void(printf("0 , 0 , 0"));
if(dat==p*q*r+)return void(printf("0 , 0 , 0"));
ri z=dat%r;if(!z)z+=r;dat-=z;dat/=r;dat+=;
ri y=dat%q;if(!y)y+=q;dat-=y;dat/=q;dat+=;
ri x=dat;
printf("%d , %d , %d",x,y,z);
}
il void ad(ri x,ri y,ri z)
{
//printf("(");print(y);printf(") -> (");print(x);printf(") : %d\n",z);
//printf("%d -> %d : %d\n",y,x,z);
edge[++ed_cnt]=(ed){x,head[y],z};head[y]=ed_cnt;edge[++ed_cnt]=(ed){y,head[x],};head[x]=ed_cnt;}
il bool bfs()
{
queue<int>Q;Q.push(S);memset(dep,,sizeof(dep));dep[S]=;
while(!Q.empty()){ri nw=Q.front();Q.pop();e(i,nw)if(w(i) && !dep[t(i)])dep[t(i)]=dep[nw]+,Q.push(t(i));}
return dep[T];
}
il int dfs(ri nw,ri flow)
{
if(nw==T || !flow)return flow;ri ret=;
for(ri &i=cur[nw];~i;i=n(i))
if(w(i) && dep[t(i)]==dep[nw]+)
{ri tmp=dfs(t(i),min(flow,w(i)));ret+=tmp,w(i)-=tmp;w(i^)+=tmp,flow-=tmp;}
return ret;
}
il int dinic(){ri ret=;while(bfs()){rp(i,S,T)cur[i]=head[i];while(int d=dfs(S,inf))ret+=d;}return ret;} int main()
{
//freopen("3227.in","r",stdin);freopen("3227.out","w",stdout);
memset(head,-,sizeof(head));p=read();q=read();r=read();d=read();S=;T=p*q*r+;
rp(i,,p)rp(j,,q){ad(nam(i,j,),S,read());}
rp(k,,r){rp(i,,p)rp(j,,q)ad(nam(i,j,k),nam(i,j,k-),read());}
rp(i,,p)rp(j,,q)ad(T,nam(i,j,r),inf);
rp(i,,p)
rp(j,,q)
rp(t,,)
{
ri to_x=i+mov_x[t],to_y=j+mov_y[t];
if(!to_x || !to_y || to_x>p || to_y>q)continue;
rp(k,,r)
{
ri tmp=k-d;if(tmp>){ad(nam(to_x,to_y,tmp),nam(i,j,k),inf);}
tmp=k+d+;if(tmp<=r){ad(nam(i,j,k+),nam(to_x,to_y,tmp),inf);}
}
}
printf("%d\n",dinic());
return ;
}

最新文章

  1. socket编程学习step1
  2. JS valueOf与字符串
  3. CSS3字体图标
  4. 【笨嘴拙舌WINDOWS】GDI对象之位图
  5. Ubuntu14.04 开启MySQL的remote access
  6. java synchronized(一)
  7. vbox磁盘空间扩容
  8. jQuery提交Json数据到Webservice,并接收返回的Json数据
  9. [Ionic] Ionic Quickstart for Windows
  10. 提升网站用户体验—WebP 图片的高效使用
  11. jQuery扩展与noConflict的用法-小示例
  12. Android开发系列(二十八):使用SubMenu创建选项菜单
  13. Android多线程下安全访问数据库
  14. java环境配置,试用和基本数据结构
  15. 最近跟mysql的自动shutdown干上了。。。
  16. SQL列中含有换行符的查找和替换方法
  17. VScode加文件头的方式
  18. socket 实现单一串口共享读写操作
  19. 网络协议 反扒机制 fidder 抓包工具
  20. Ex 6_12 凸多边形的最优三角剖分..._第六次作业

热门文章

  1. intellij idea怎么设置java帮助文档
  2. C#设置Excel行高、列宽
  3. 3、.net core 部署到IIS
  4. saltStack 状态模块(状态间的关系)
  5. 《attention is all you need》解读
  6. SuperSocket证书节点新增配置属性 &quot;storeLocation&quot;
  7. xml path 列转行实例
  8. HTML 标签:常规元素和空元素
  9. springmvc 多文件/文件夹上传 下载
  10. Spring Boot JPA 懒加载