洛谷$P3227\ [HNOI2013]$切糕 网络流
2024-10-08 06:10:24
正解:网络流
解题报告:
日常看不懂题系列,,,$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 ;
}
最新文章
- socket编程学习step1
- JS valueOf与字符串
- CSS3字体图标
- 【笨嘴拙舌WINDOWS】GDI对象之位图
- Ubuntu14.04 开启MySQL的remote access
- java synchronized(一)
- vbox磁盘空间扩容
- jQuery提交Json数据到Webservice,并接收返回的Json数据
- [Ionic] Ionic Quickstart for Windows
- 提升网站用户体验—WebP 图片的高效使用
- jQuery扩展与noConflict的用法-小示例
- Android开发系列(二十八):使用SubMenu创建选项菜单
- Android多线程下安全访问数据库
- java环境配置,试用和基本数据结构
- 最近跟mysql的自动shutdown干上了。。。
- SQL列中含有换行符的查找和替换方法
- VScode加文件头的方式
- socket 实现单一串口共享读写操作
- 网络协议 反扒机制 fidder 抓包工具
- Ex 6_12 凸多边形的最优三角剖分..._第六次作业