题解：
网络流
最大权独立集=总和-最大流
然后构图
代码：
#include<cstdio> #include<cmath> #include<cstring> #include<algorithm> using namespace std; const int N=100005; int num,k,dis[N],t,ans,q[N],fi[N],ne[N],ans1,zz[N],sl[N],n,m,a[55][55]; void jb(int x,int y,int z) { ne[num]=fi[x]; fi[x]=num; zz[num]=y; sl[num++]=z; swap(x,y); z=0; ne[num]=fi[x]; fi[x]=num; zz[num]=y; sl[num++]=z; } int bfs() { memset(dis,0xff,sizeof dis); dis[1]=0; int l=0,r=1; q[1]=1; while (l<r) { int j=q[++l]; for (int i=fi[j];i!=-1;i=ne[i]) if (dis[zz[i]]<0&&sl[i]>0) { dis[zz[i]]=dis[j]+1; q[++r]=zz[i]; } } if (dis[n]>0)return 1; return 0; } int find(int x,int low) { int b=0; if (x==n)return low; for (int i=fi[x];i!=-1;i=ne[i]) if (sl[i]>0&&dis[zz[i]]==dis[x]+1&&(b=find(zz[i],min(low,sl[i])))) { sl[i]-=b; sl[i^1]+=b; return b; } return 0; } void doit() { memset(fi,-1,sizeof fi); memset(a,0,sizeof a); memset(sl,0,sizeof sl); ans1=ans=0;num=0; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) { scanf("%d",&a[i][j]); ans1+=a[i][j]; if ((i+j)&1)jb(1,(i-1)*m+j+1,a[i][j]); else jb((i-1)*m+j+1,n*m+2,a[i][j]); } for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if ((i+j)&1) { if (i!=1)jb((i-1)*m+j+1,(i-2)*m+j+1,1e9); if (i!=n)jb((i-1)*m+j+1,i*m+j+1,1e9); if (j!=1)jb((i-1)*m+j+1,(i-1)*m+j,1e9); if (j!=m)jb((i-1)*m+j+1,(i-1)*m+j+2,1e9); } int t;ans=0; n=n*m+2; while (bfs()) while (t=find(1,1e9))ans+=t; printf("%d ",ans1-ans); } int main() { while (~scanf("%d%d",&n,&m))doit(); }