BZOJ 3144: [Hnoi2013]切糕

3144: [Hnoi2013]切糕

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 1495 Solved: 819
[Submit][Status][Discuss]

Description

Input

第一行是三个正整数P,Q,R，表示切糕的长P、宽Q、高R。第二行有一个非负整数D，表示光滑性要求。接下来是R个P行Q列的矩阵，第z个矩阵的第x行第y列是v(x,y,z) (1≤x≤P, 1≤y≤Q, 1≤z≤R)。
100%的数据满足P,Q,R≤40，0≤D≤R，且给出的所有的不和谐值不超过1000。

Output

仅包含一个整数，表示在合法基础上最小的总不和谐值。

Sample Input

2 2 2
1
6 1
6 1
2 6
2 6

Sample Output

HINT

最佳切面的f为f(1,1)=f(2,1)=2,f(1,2)=f(2,2)=1

Source

分析：

限制距离模型：

可以把题意看成有p*q个网格，每个网格有r个点，要在每个格子中选一个点，并且相邻的格子选择的点距离不超过d，求最小代价...

考虑如果没有距离限制怎么建图...把每个格子拆成r个点，串成一条链和ST相连，求最小割就是答案...

现在有了距离限制...怎么办？？最常用的限制方法就是添加容量为+∞的边...

我们把(i,j,k)向(i',j',k-d)(相邻的格子)连边...这个正确性画一下图YY一下就好...

代码：

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 //by NeighThorn

 #define inf 0x3f3f3f3f

 using namespace std;

 const int maxn=+,maxm=+;

 int n,m,h,d,S,T,cnt,hd[maxn],fl[maxm],to[maxm],nxt[maxm],pos[maxn];

 int mv[][]={,,,-,,,-,};

 inline bool bfs(void){

     memset(pos,-,sizeof(pos));

     int head=,tail=,q[maxn];

     q[]=S,pos[S]=;

     while(head<=tail){

         int top=q[head++];

         for(int i=hd[top];i!=-;i=nxt[i])

             if(pos[to[i]]==-&&fl[i])

                 pos[to[i]]=pos[top]+,q[++tail]=to[i];

     }

     return pos[T]!=-;

 }

 inline int find(int v,int f){

     if(v==T)

         return f;

     int res=,t;

     for(int i=hd[v];i!=-&&f>res;i=nxt[i])

         if(pos[to[i]]==pos[v]+&&fl[i])

             t=find(to[i],min(fl[i],f-res)),res+=t,fl[i]-=t,fl[i^]+=t;

     if(!res)

         pos[v]=-;

     return res;

 }

 inline int dinic(void){

     int res=,t;

     while(bfs())

         while(t=find(S,inf))

             res+=t;

     return res;

 }

 inline void add(int s,int x,int y){

     fl[cnt]=s;to[cnt]=y;nxt[cnt]=hd[x];hd[x]=cnt++;

     fl[cnt]=;to[cnt]=x;nxt[cnt]=hd[y];hd[y]=cnt++;

 }

 signed main(void){

     // freopen("in.txt","r",stdin);

     memset(hd,-,sizeof(hd));

     scanf("%d%d%d%d",&n,&m,&h,&d);

     S=,T=n*m*h+;

     for(int k=,x;k<=h;k++)

         for(int i=;i<=n;i++)

             for(int j=;j<=m;j++){

                 scanf("%d",&x);

                 if(k==)

                     add(x,S,((i-)*m+j-)*h+k);

                 else

                     add(x,((i-)*m+j-)*h+k-,((i-)*m+j-)*h+k);

                 if(k==h)

                     add(inf,((i-)*m+j-)*h+k,T);

             }

     for(int i=;i<=n;i++)

         for(int j=;j<=m;j++)

             for(int k=d+;k<=h;k++)

                 for(int t=;t<;t++){

                     int x=i+mv[t][],y=j+mv[t][];

                     if(x>=&&x<=n&&y>=&&y<=m)

                         add(inf,((i-)*m+j-)*h+k,((x-)*m+y-)*h+k-d);

                 }

     printf("%d\n",dinic());

     return ;

 }//Cap ou pas cap. Cap.

By NeighThorn

巴特西