由于最大流是贴dinic模版的所以就只放主函数代码了,这题想了下,是个最小割,现求出每个\p[i]-v0\的和记为s1,然后对每个点\p[i]-v1\-\p[i]-v0\是它的权值,所有权值为负的点权值相反数之和为sum,如果这个是正的,那么就连这个点到汇点一条权值为这个的边,否则就从源点连条权值为这个相反数的边到这个店,然后对于每个点,连条到与之相邻的点一条边,权值是p[i]-p[j]的绝对值,然后最小割+s1-sum就是答案,仔细推敲下吧。
int main() { int pro=0; scanf("%d",&T); while(T--) { sum=0; int s1=0; scanf("%d%d%d%d",&n,&m,&v0,&v1); for(int i=0;i<n;i++) for(int j=0;j<m;j++) { scanf("%d",&p[i][j]); s1+=abs(p[i][j]-v0); } s=n*m,t=s+1; dinic.init(s,t); for(int i=0;i<n;i++) for(int j=0;j<m;j++) { int nu=i*m+j; int mm=abs(p[i][j]-v1)-abs(p[i][j]-v0); if(mm<0) sum+=(-mm); if(mm>0) dinic.add_edge(nu,t,mm); else dinic.add_edge(s,nu,-mm); } for(int i=0;i<n;i++) for(int j=0;j<m;j++) { int nu=i*m+j; if(i>0) dinic.add_edge(nu,nu-m,abs(p[i][j]-p[i-1][j])); if(i<n-1) dinic.add_edge(nu,nu+m,abs(p[i][j]-p[i+1][j])); if(j>0) dinic.add_edge(nu,nu-1,abs(p[i][j]-p[i][j-1])); if(j<m-1) dinic.add_edge(nu,nu+1,abs(p[i][j]-p[i][j+1])); } printf("Case %d:\n",++pro); printf("%d\n",s1+dinic.flow()-sum); if(T) puts(""); } return 0; }