洛谷$P3227\ [HNOI2013]$切糕 网络流
正解:网络流
解题报告:
日常看不懂题系列,,,$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=300000+10,inf=1e9;
int S,T,ed_cnt=-1,head[N],as,cur[N],dep[N],p,q,r,d;
int mov_x[4]={0,0,1,-1},mov_y[4]={1,-1,0,0};
struct ed{int to,nxt,wei;}edge[N<<2];
il int read()
{
rc ch=gc;ri x=0;rb y=1;
while(ch!='-' && (ch>'9' || ch<'0'))ch=gc;
if(ch=='-')ch=gc,y=0;
while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc;
return y?x:-x;
}
il int nam(ri x,ri y,ri z){return ((x-1)*q+y-1)*r+z;}
il void print(ri dat)
{
if(!dat)return void(printf("0 , 0 , 0"));
if(dat==p*q*r+1)return void(printf("0 , 0 , 0"));
ri z=dat%r;if(!z)z+=r;dat-=z;dat/=r;dat+=1;
ri y=dat%q;if(!y)y+=q;dat-=y;dat/=q;dat+=1;
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],0};head[x]=ed_cnt;}
il bool bfs()
{
queue<int>Q;Q.push(S);memset(dep,0,sizeof(dep));dep[S]=1;
while(!Q.empty()){ri nw=Q.front();Q.pop();e(i,nw)if(w(i) && !dep[t(i)])dep[t(i)]=dep[nw]+1,Q.push(t(i));}
return dep[T];
}
il int dfs(ri nw,ri flow)
{
if(nw==T || !flow)return flow;ri ret=0;
for(ri &i=cur[nw];~i;i=n(i))
if(w(i) && dep[t(i)]==dep[nw]+1)
{ri tmp=dfs(t(i),min(flow,w(i)));ret+=tmp,w(i)-=tmp;w(i^1)+=tmp,flow-=tmp;}
return ret;
}
il int dinic(){ri ret=0;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,-1,sizeof(head));p=read();q=read();r=read();d=read();S=0;T=p*q*r+1;
rp(i,1,p)rp(j,1,q){ad(nam(i,j,1),S,read());}
rp(k,2,r){rp(i,1,p)rp(j,1,q)ad(nam(i,j,k),nam(i,j,k-1),read());}
rp(i,1,p)rp(j,1,q)ad(T,nam(i,j,r),inf);
rp(i,1,p)
rp(j,1,q)
rp(t,0,3)
{
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,1,r)
{
ri tmp=k-d;if(tmp>0){ad(nam(to_x,to_y,tmp),nam(i,j,k),inf);}
tmp=k+d+1;if(tmp<=r){ad(nam(i,j,k+1),nam(to_x,to_y,tmp),inf);}
}
}
printf("%d\n",dinic());
return 0;
}