一个矩阵,每个格子分配一个数,不同的数字,代价不同,要求相邻格子数字差小等于d
求最小代价。
我猜肯定有人看题目就想到最小割了,然后一看题面理科否决了自己的这个想法……
没错,就是最小割……
你是否还记得,在第一篇网络流题解中,我们了解了网络流最重要的是“限制”二字。
我们在这道题中,先把限制放宽,考虑在不限制编号差小于等于d的情况下,怎么办?
我们俯视这个立方体,把每个位置的所有层的点由下到上连起来,变成P*Q个点串,底面上所有的点连源点,顶面上所有点连汇点,权值反应在边上,求最小割即可。
那我们现在有限制了,怎么办?
一个思路是,我们想办法强制如果相邻两个点割开的位置距离大于d,那就绝对不能割开这两个点,所以我们有一个这样的脸变方法:从当前点串的i号点向相邻点串的i-d号点连一条正无穷的边,这样呢,当我们两个相邻的点串有割开距离大于d的时候,自然会有一条正无穷的边让我们割不开,于是跑最小割就可以合法了!
代码:
1 #include<bits/stdc++.h> 2 #define ms(a,x) memset(a,x,sizeof(a)) 3 using namespace std;int tot=0; 4 const int N=100005,M=45,inf=0x3f3f3f3f; 5 struct node{int y,z,nxt;}e[N*10]; 6 int n,m,k,D,S,T,c=1,f[M][M][M],h[N],d[N]; 7 int q[N],xx[4]={0,0,1,-1},yy[4]={1,-1,0,0}; 8 int p(int x,int y,int z){ 9 return z==0?0:(z-1)*n*m+(x-1)*m+y; 10 } void add(int x,int y,int z){ 11 e[++c]=(node){y,z,h[x]};h[x]=c; 12 e[++c]=(node){x,0,h[y]};h[y]=c; 13 } bool bfs(){ 14 int f=1,t=0;ms(d,-1); 15 q[++t]=S;d[S]=0; 16 while(f<=t){ 17 int x=q[f++]; 18 for(int i=h[x],y;i;i=e[i].nxt) 19 if(d[y=e[i].y]==-1&&e[i].z) 20 d[y]=d[x]+1,q[++t]=y; 21 } return (d[T]!=-1); 22 } int dfs(int x,int f){ 23 if(x==T) return f;int w,tmp=0; 24 for(int i=h[x],y;i;i=e[i].nxt) 25 if(d[y=e[i].y]==d[x]+1&&e[i].z){ 26 w=dfs(y,min(e[i].z,f-tmp)); 27 if(!w) d[y]=-1; 28 e[i].z-=w;e[i^1].z+=w; 29 tmp+=w;if(tmp==f) return f; 30 } return tmp; 31 } void dinic(){ 32 while(bfs()) tot+=dfs(S,inf); 33 } void build(){ 34 for(int i=1;i<=n;i++) 35 for(int j=1;j<=m;add(p(i,j,k),T,inf),j++) 36 for(int v=1;v<=k;v++){ 37 add(p(i,j,v-1),p(i,j,v),f[i][j][v]); 38 if(v>D) 39 for(int u=0;u<4;u++){ 40 int nx=i+xx[u],ny=j+yy[u]; 41 if(nx<1||ny<1||nx>n||ny>m) continue; 42 add(p(i,j,v),p(nx,ny,v-D),inf); 43 } 44 } 45 } 46 int main(){ 47 scanf("%d%d%d",&n,&m,&k); 48 S=0;T=n*m*k+1;scanf("%d",&D); 49 for(int i=1;i<=k;i++) 50 for(int j=1;j<=n;j++) 51 for(int v=1;v<=m;v++) 52 scanf("%d",&f[j][v][i]); 53 build();dinic(); 54 printf("%d\n",tot);return 0; 55 }
原文:https://www.cnblogs.com/Alan-Luo/p/10252070.html