题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3144

题目分类：最小割，网络流

题意：

要求你对n*m的矩阵的每一个元素求一个函数f(x,y)(1<=f(x,y)<=q)，要求使得sigma(val(x,y,f(x,y)))最小，val函数会以q个矩阵的形式给出。矩阵中相邻元素的函数值需要相差不超过k。

题解：

进行最小割建模。

每个元素对应q+1个点，建出从原点开始依次经过这q+1个点直到汇点的一条链，权值为对应的val函数权值。这是不满足相邻元素函数值差不超过k的最小割建模。

为了满足函数值差不超过k的要求，我们在相邻元素对应的链之间从所有的q'向相邻的（q'-k）连一条边权值无穷大，这使得无法通过割去q'之后的边和相邻的（q'-k）之前的边来构成一个割，从而满足了限制。

程序：

#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxl=200000;
int st[maxl],ed;
struct node
{
    int next,to,fl,opt;
}g[10*maxl];
inline void add(int x,int y,int z)
{
//	printf("%d %d %d\n",x,y,z);
    ed++;
    g[ed].to=y;
    g[ed].next=st[x];
    g[ed].fl=z;
    g[ed].opt=ed+1;
    st[x]=ed;
    ed++;
    g[ed].to=x;
    g[ed].next=st[y];
    g[ed].fl=0;
    g[ed].opt=ed-1;
    st[y]=ed;
}
int x1,x2,x3,lev[maxl],des;
inline bool makelev()
{
    queue<int>q;
    q.push(0);
    memset(lev,-1,sizeof(lev));
    lev[0]=1;
    while (!q.empty())
    {
        x1=q.front();q.pop();//printf("%d ",x1);
        for (int i=st[x1];i!=0;i=g[i].next)
        {
            if(lev[g[i].to]==-1&&g[i].fl!=0)
            {
                q.push(g[i].to);
                lev[g[i].to]=lev[x1]+1;
                if(g[i].to==des){return true;}
            }
        }
    }return false;
}
int stap,sta[maxl],spre[maxl],stae[maxl];
int maxflow;
inline void extend()
{
    int del;
    stap=1;
    sta[1]=0;
    for (int i=0;i<=des;i++)
    {
        spre[i]=st[i];//printf("%d %d\n",i,st[i]);
    }
    while (stap!=0)
    {
        x1=sta[stap];
    //  printf("%d\n",x1);
        if(x1!=des)
        {
            for (;spre[x1]!=0;spre[x1]=g[spre[x1]].next)
            {
                if(g[spre[x1]].fl!=0&&lev[x1]+1==lev[g[spre[x1]].to])
                {
                    break;
                }
            }
            if(spre[x1]!=0)
            {
                stap++;
                stae[stap]=spre[x1];
                sta[stap]=g[spre[x1]].to;
            }
            else
            {
                stap--;lev[x1]=0;
            }
        }
        else
        {
            del=1050000000;
            for (int i=stap;i>=2;i--)
            {
                del=min(del,g[stae[i]].fl);
            }//printf("%d\n",del);
            maxflow+=del;
            for (int i=stap;i>=2;i--)
            {
                g[stae[i]].fl-=del;
                g[g[stae[i]].opt].fl+=del;
                if(g[stae[i]].fl==0)stap=i-1;
            }
        }
    }
}
inline void dinic()
{
    maxflow=0;
    while (makelev())extend();
}
int n,m,q,d,f[50][50][50],num[100][100][100],cnt;
int main()
{
	scanf("%d %d %d",&n,&m,&q);
	scanf("%d",&d);
	des=n*m*(q+1)+1;
	for (int i=1;i<=q+1;i++)
	{
		for (int j=1;j<=n;j++)
		{
			for (int k=1;k<=m;k++)
			{
				cnt++;
				num[j][k][i]=cnt;
			}
		}
	}
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++)
		{
			add(0,num[i][j][1],1050000000);add(num[i][j][q+1],des,105000000);
		}
	}
	for (int i=1;i<=q;i++)
	{
		for (int j=1;j<=n;j++)
		{
			for (int k=1;k<=m;k++)
			{
				scanf("%d",&f[j][k][i]);
				add(num[j][k][i],num[j][k][i+1],f[j][k][i]);
				if(num[j+1][k][i+d]!=0)
				{
					add(num[j+1][k][i+d],num[j][k][i],1050000000);
				}
				if(num[j][k+1][i+d]!=0)
				{
					add(num[j][k+1][i+d],num[j][k][i],1050000000);
				}
				if(num[j-1][k][i+d]!=0)
				{
					add(num[j-1][k][i+d],num[j][k][i],1050000000);
				}
				if(num[j][k-1][i+d]!=0)
				{
					add(num[j][k-1][i+d],num[j][k][i],1050000000);
				}
			}
		}
	}
	dinic();
	printf("%d\n",maxflow);
    return 0;
}