总算做了一道2011以后的省选题了……

原题：

图片题面好评！

P,Q,R≤40，0≤D≤R，给出的所有的不和谐值不超过1000。

文本样例好评！

 

恩这个是听妹主席讲过后会写的，首先把每个点拆成链，那么割掉这个链上的某条边就表示这个点选了某个权值，边的流量就是这个点设成这个值的花费，表示要花费掉这些代价来把这条边割掉

相邻两个点的值之差<=d怎么搞呐，假设两个相邻的点x，y，那么x的第i个点往y的i-d个点连oo的边，即可，大概就像酱紫：

 

 如果有两个被割掉的线段距离超过d，就依然存在一条路径从s到t，就要继续割

差不多是酱紫：

恩就酱

代码：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 using namespace std; 7 const int oo=168430090; 8 int rd(){
    int z=0,mk=1;  char ch=getchar(); 9     while(ch<'0'||ch>'9'){
    if(ch=='-')mk=-1;  ch=getchar();}10     while(ch>='0'&&ch<='9'){z=(z<<3)+(z<<1)+ch-'0';  ch=getchar();}11     return z*mk;12 }13 struct ddd{
    int nxt,y,v,rvs;}e[2100000];  int lk[66100],ltp=0;14 inline void ist(int x,int y,int z){15     e[++ltp].nxt=lk[x],lk[x]=ltp,e[ltp].y=y,e[ltp].v=z,e[ltp].rvs=ltp+1;16     e[++ltp].nxt=lk[y],lk[y]=ltp,e[ltp].y=x,e[ltp].v=0,e[ltp].rvs=ltp-1;17 }18 const int fx[4]={
    1,-1,0,0},fy[4]={
    0,0,1,-1};19 int n,m,h,d;  int N;  int s,t;20 int lvl[66100];21 int q[66100],hd=0;22 bool gtlvl(){23     memset(lvl,0,sizeof(lvl));24     q[hd=1]=s,lvl[s]=1;25     for(int k=1;k<=hd;++k)26         for(int i=lk[q[k]];i;i=e[i].nxt)if(e[i].v && !lvl[e[i].y])27             lvl[e[i].y]=lvl[q[k]]+1,q[++hd]=e[i].y;28     return lvl[t];29 }30 int mxflw(int x,int y){31     if(x==t)  return y;32     int bwl=0,flw=0;33     for(int i=lk[x];i && bwl
           
            =1 && x+fx[z]<=n && y+fy[z]>=1 && y+fy[z]<=m;48 }49 inline int gtid(int x,int y,int z){ return z*N+(x-1)*m+y;}50 int main(){ //freopen("ddd.in","r",stdin);51 cin>>n>>m>>h>>d; N=n*m; s=0,t=N*(h+1)+1;52 for(int k=1;k<=h;++k)for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)53 ist(gtid(i,j,k-1),gtid(i,j,k),rd());54 for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)for(int k=0;k<4;++k)if(chck(i,j,k))55 for(int p=1;p+d<=h;++p){56 ist(gtid(i,j,p+d),gtid(i+fx[k],j+fy[k],p),oo);57 ist(gtid(i+fx[k],j+fy[k],p+d),gtid(i,j,p),oo);58 }59 for(int i=1;i<=n;++i)for(int j=1;j<=m;++j) ist(s,gtid(i,j,0),oo),ist(gtid(i,j,h),t,oo);60 cout<
            
             <