相邻点之间连接权值为正无穷的边，可以得到一个二分图，对于任意一点，若选择该点，则必须放弃与该点相连的所有点。加上源点和汇点，即成为一个最小割模型。答案即为总数减去最小割。
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #define min(x,y) x<y?x:y
5 using namespace std;
6 const int N=440;
7 const int M=3300;
8 const int INF=100000000;
9 int g[N],dis[N],q[N];
10 int en[M],val[M],next[M],rev[M];
11 int n,m,S,T,tot,ans;
12 int addedge(int a,int b,int c){
13 tot++;en[tot]=b;val[tot]=c;next[tot]=g[a];g[a]=tot;
14 tot++;en[tot]=a;val[tot]=0;next[tot]=g[b];g[b]=tot;
15 rev[g[a]]=g[b];
16 rev[g[b]]=g[a];
17 return 0;
18 }
19 int init(){
20 int i,j,a;
21 if(scanf("%d",&n)==EOF)
22 return 0;
23 S=1;T=n*n+2;tot=0;ans=0;
24 memset(g,0,sizeof(g));
25 for(i=1;i<=n;i++)
26 for(j=1;j<=n;j++){
27 scanf("%d",&a);
28 ans+=a;
29 if((i+j)%2)
30 addedge((i-1)*n+j+1,T,a);
31 else{
32 addedge(S,(i-1)*n+j+1,a);
33 if(i>1)
34 addedge((i-1)*n+j+1,(i-2)*n+j+1,INF);
35 if(j>1)
36 addedge((i-1)*n+j+1,(i-1)*n+j,INF);
37 if(i<n)
38 addedge((i-1)*n+j+1,i*n+j+1,INF);
39 if(j<n)
40 addedge((i-1)*n+j+1,(i-1)*n+j+2,INF);
41 }
42 }
43 return 1;
44 }
45 int build(){
46 int hp=0,tp=0;
47 memset(dis,0,sizeof(dis));
48 q[0]=S;dis[S]=1;
49 for(hp=0;hp<=tp;hp++){
50 int k=q[hp];
51 for(int p=g[k];p;p=next[p]){
52 if(val[p]>0 && dis[en[p]]==0){
53 q[++tp]=en[p];
54 dis[q[tp]]=dis[k]+1;
55 if(q[tp]==T)return 1;
56 }
57 }
58 }
59 return 0;
60 }
61 int find(int s,int aug){
62 int flow=0;
63 if(s==T || aug==0) return aug;
64 for(int p=g[s];p;p=next[p]){
65 if(val[p]>0 && dis[en[p]]-1==dis[s]){
66 int k=find(en[p],min(val[p],aug));
67 flow+=k;
68 aug-=k;
69 val[p]-=k;
70 val[rev[p]]+=k;
71 if(aug==0) return flow;
72 }
73 }
74 return flow;
75 }
76 int work(){
77 while(build()){
78 ans-=find(S,INF);
79 }
80 printf("%d\n",ans);
81 return 0;
82 }
83 int main(){
84 while(init())
85 work();
86 return 0;
87 }