河北网站seo,wordpress首页404伪静态,代理记账网站怎么做,网站建设电子合同题意: n ∗ m n*m n∗m的矩阵,每个点可以选择一个值 a i , j k a_{i,j}k ai,jk,然后你能获得 w ( i , j , k ) w(i,j,k) w(i,j,k)的得分#xff0c;但是相邻两点之间的差值有限制#xff0c;让你求最大得分。
考虑最小割。
每个点 ( i , j ) (i,j) (i,j)弄出一条长为 R…题意: n ∗ m n*m n∗m的矩阵,每个点可以选择一个值 a i , j k a_{i,j}k ai,jk,然后你能获得 w ( i , j , k ) w(i,j,k) w(i,j,k)的得分但是相邻两点之间的差值有限制让你求最大得分。
考虑最小割。
每个点 ( i , j ) (i,j) (i,j)弄出一条长为 R 1 R1 R1的链其中 k − k 1 k - k1 k−k1的流量为 w ( i , j , k ) w(i,j,k) w(i,j,k)。
考虑限制只需要从这条链的 k k k到相邻一条链的 k − d k-d k−d连一无穷大的边因为如果相邻的链选择的点 k − d k-d k−d那么就会有流量剩余因此就能进行限制了。
#includebits/stdc.h
#define rep(i,x,y) for(int ix;iy;i)
#define dwn(i,x,y) for(int ix;iy;i--)
#define ll long long
using namespace std;
templatetypename Tinline void qr(T x){x0;int f0;char sgetchar();while(!isdigit(s))f|s-,sgetchar();while(isdigit(s))xx*10s-48,sgetchar();xf?-x:x;
}
int cc0,buf[31];
templatetypename Tinline void qw(T x){if(x0)putchar(-),x-x;do{buf[cc]int(x%10);x/10;}while(x);while(cc)putchar(buf[cc--]0);
}
const int N5e510;
int n,m,k,d;
int h[N],st,ed,cur[N];
int tot1,hd[N],ver[N*5],nxt[N*5],w[N*5];
int a[50][50][50],id[50][50][50],cnt;
void add(int x,int y,int z){tot;ver[tot]y;w[tot]z;nxt[tot]hd[x];hd[x]tot;
}
void link(int x,int y,int z){add(x,y,z),add(y,x,0);
}
bool bt_h(){memset(h,0,sizeof(h));h[st]1;queueintq;q.push(st);while(q.size()){int xq.front();q.pop();for(int ihd[x];i;inxt[i]){int yver[i];if(w[i]!h[y]){h[y]h[x]1;q.push(y);}}}return h[ed];
}
int findflow(int x,int f){if(xed)return f;int resf,tt;for(int icur[x];i;inxt[i]){int yver[i];if(w[i]h[y]h[x]1){ttfindflow(y,min(res,w[i]));w[i]-tt,w[i^1]tt;res-tt;if(!res)break;}}if(resf)h[x]0;return f-res;
}
int dicnic(){int ans0;while(bt_h()){memcpy(cur,hd,sizeof(cur));ansfindflow(st,1e9);}return ans;
}
const int dx[4]{-1,1,0,0};
const int dy[4]{0,0,-1,1};
void solve(){qr(n),qr(m),qr(k),qr(d);rep(ki,1,k){rep(i,1,n)rep(j,1,m)qr(a[ki][i][j]);}rep(ki,1,k1){rep(i,1,n)rep(j,1,m)id[ki][i][j]cnt;}stcnt1,edst1;rep(i,1,n)rep(j,1,m){link(st,id[1][i][j],1e7);link(id[k1][i][j],ed,1e7);}rep(ki,1,k){rep(i,1,n)rep(j,1,m){link(id[ki][i][j],id[ki1][i][j],a[ki][i][j]);}if(kid){rep(i,1,n)rep(j,1,m){rep(t,0,3){int xidx[t],yjdy[t];if(1xxn1yym){link(id[ki][i][j],id[ki-d][x][y],1e7);}}}}}qw(dicnic());puts();
}
int main(){int tt;tt1;while(tt--)solve();return 0;
}
