1475: 方格取数

Time Limit: 5 Sec  Memory Limit: 64 MB

Submit: 578  Solved: 309

[][][]

Description

在一个n*n的方格里，每个格子里都有一个正整数。从中取出若干数，使得任意两个取出的数所在格子没有公共边，且取出的数的总和尽量大。

Input

第一行一个数n；（n<=30） 接下来n行每行n个数描述一个方阵

Output

仅一个数，即最大和

Sample Input

2

1 2

3 5

Sample Output

6

HINT

 

Source

 

题解：又是一个网络流= =，貌似学到了一个新的建图模式——将两个块的分居两端，分别与源和汇相连，然后中间直接相互冲突的（比如本题中相邻的）连上正无穷边，然后网络流后再用总和剪下= =，然后没了，感觉网络流这东西越学越神奇QAQ么么哒

1 /************************************************************** 2     Problem: 1475 3     User: HansBug 4     Language: Pascal 5     Result: Accepted 6     Time:304 ms 7     Memory:612 kb 8 ****************************************************************/ 9  10 type11     point=^node;12     node=record13                g,w:longint;14                anti,next:point;15     end;16 var17    i,j,k,l,m,n,s,t,flow:longint;18    a,e:array[0..10000] of point;19    b,c,d:array[0..10000] of longint;20 function min(x,y:longint):longint;21          begin22               if x
      
       nil do40                                 begin41                                      if (p^.w<>0) and (c[p^.g]=maxlongint) then42                                         begin43                                              e[p^.g]:=p;44                                              c[p^.g]:=c[d[f]]+1;45                                              d[r]:=p^.g;inc(r);46                                         end;47                                      p:=p^.next;48                                 end;49                           inc(f);50                      end;51                exit(c[t]<>maxlongint);52           end;53 procedure deal;54           begin55                i:=t;l:=maxlongint;56                while i<>s do57                      begin58                           l:=min(e[i]^.w,l);59                           i:=e[i]^.anti^.g;60                      end;61                dec(flow,l);i:=t;62                while i<>s do63                      begin64                           if e[i]^.w<>maxlongint then dec(e[i]^.w,l);65                           if e[i]^.anti^.w<>maxlongint then inc(e[i]^.anti^.w,l);66                           i:=e[i]^.anti^.g;67                      end;68           end;69 begin70      readln(n);flow:=0;s:=1;t:=n*n+2;71      for i:=1 to n*n+2 do a[i]:=nil;72      for i:=1 to n do73          for j:=1 to n do74              begin75                   read(k);inc(flow,k);76                   if odd(i+j) then add(1,(i-1)*n+j+1,k) else add((i-1)*n+j+1,n*n+2,k);77                   if odd(i+j) then78                      begin79                           if i>1 then add((i-1)*n+j+1,(i-2)*n+j+1,maxlongint);80                           if i
       
        1 then add((i-1)*n+j+1,(i-1)*n+j,maxlongint);82                           if j