你要在一个n*m的矩阵中填上小于k的整数,每个位置填每个数有对应的代价,且相邻数大小之差要小于d,求最小代价
\(n,m,k \le 40\)
先不管那个限制
考虑把S向每个位置的1连边,然后每个位置依次连k条边向自己,最后连向T
边权都为选的代价,于是求个最小割就是答案了
现在有了限制,我们就把所有大于d的值为i的点向其四联通的值为i-d的点连一条inf的边
这样就一定满足限制了
#include #include #include #include #include #include #include #include #include #include #define ls p<<1 #define rs p<<1|1 using namespace std; typedef long long ll; const int mxn=1e5+5,inf=1e9; int n,m,k,d,S,T,cnt,ans,hd[mxn]; int a[55][55][55],cur[mxn],dep[mxn]; int dx[5]={0,0,1,-1},dy[5]={1,-1,0,0}; inline int read() { char c=getchar(); int x=0,f=1; while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();} while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();} return x*f; } inline void chkmax(int &x,int y) {if(xy) x=y;} struct ed { int to,nxt,w; }t[mxn<<1]; inline void add(int u,int v,int w) { t[++cnt]=(ed) {v,hd[u],w}; hd[u]=cnt; t[++cnt]=(ed) {u,hd[v],0}; hd[v]=cnt; } int bfs() { queue q; q.push(S); memset(dep,0,sizeof(dep)); dep[S]=1; for(int i=S;i<=T;++i) cur[i]=hd[i]; while(!q.empty()) { int u=q.front(); q.pop(); for(int i=hd[u];i!=-1;i=t[i].nxt) { int v=t[i].to; if(!dep[v]&&t[i].w>0) dep[v]=dep[u]+1,q.push(v); } } return dep[T]; } int dfs(int u,int f) { if(u==T) return f; for(int &i=cur[u];i!=-1;i=t[i].nxt) { int v=t[i].to; if(dep[v]==dep[u]+1&&t[i].w>0) { int tp=dfs(v,min(f,t[i].w)); if(tp>0) { t[i].w-=tp; t[i^1].w+=tp; return tp; } } } return 0; } void Dinic() { while(bfs()) while(int tp=dfs(S,inf)) ans+=tp; } int get(int h,int x,int y) { return ((h-1)*n+x-1)*m+y; } int main() { memset(hd,-1,sizeof(hd)); cnt=-1; n=read(); m=read(); k=read(); d=read(); T=2*n*m*k+1; for(int x=1;x<=k;++x) for(int y=1;y<=n;++y) for(int z=1;z<=m;++z) a[x][y][z]=read(); for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) { add(S,get(1,i,j),a[1][i][j]); add(get(k,i,j),T,inf); for(int h=2;h<=k;++h) { add(get(h-1,i,j),get(h,i,j),a[h][i][j]); if(h<=d) continue ; for(int p=0;p<4;++p) { int tx=i+dx[p],ty=j+dy[p]; if(tx<1||ty<1||tx>n||ty>m) continue ; add(get(h,i,j),get(h-d,tx,ty),inf); } } } Dinic(); printf("%d",ans); return 0; }