终于忙完期末考试了，即将进入愉快的暑假（虽然暑假作业奇多，但好歹终于能有大量时间刷题了）

先把上次新一类最小割留下的一道题目A了复习一下；

题目看起来很复杂，实际上和bzoj2132是同一个类型的

用S集合表示放正能量，T集合表示放负能量（可自行参照上一篇文章）

只是有几个不同点：

1. 有些点是已经确定为S或T集合中的点

2. 选择点属于S或者属于T都是没有收益的

对于未知的问题我们要转化为已知的问题来求解

首先我们来处理2，考虑到割是我们所得不到的收益，

于是我们可以把每个点选择属于S或者属于T产生的收益都当做是个1，

也就是对于每个点i，连接s--->i, i--->t 容量为1；

最后ans=n*n*n（抵消我们之前强加的收益）+图中的边数-mincut;

下面就是1没有解决了，考虑到割是我们所得不到的收益，

所以，对于那些已经确定为S集合中的点（T集合同理），我们只要使

s--->i 容量为inf，也就让这条边一定不成为割边，那么就满足了这个点的确定性；

好了，即使是立体的，依然可以黑白染色划分二分图，所以其余实现细节类似bzoj2132，这里不加赘述。

1 const inf=100000007;  2       dx:array[1..6] of integer=(-1,1,0,0,0,0);  3       dy:array[1..6] of integer=(0,0,-1,1,0,0);  4       dz:array[1..6] of integer=(0,0,0,0,-1,1);  5 type node=record  6        next,flow,point:longint;  7      end;  8   9 var edge:array[0..2000010] of node; 10     h,numh,p,cur,d,pre:array[0..64010] of longint; 11     num:array[0..41,0..41,0..41] of longint; 12     t,len,i,j,n,k,x,y,z,m,ans,sum:longint; 13     s:ansistring; 14  15 function min(a,b:longint):longint; 16   begin 17     if a>b then exit(b) else exit(a); 18   end; 19  20 procedure add(x,y,f:longint); 21   begin 22     inc(len); 23     edge[len].point:=y; 24     edge[len].flow:=f; 25     edge[len].next:=p[x]; 26     p[x]:=len; 27   end; 28  29 function sap:longint; 30   var u,i,j,q,neck,tmp:longint; 31   begin 32     numh[0]:=t+1; 33     for i:=0 to t do 34       cur[i]:=p[i]; 35     u:=0; 36     sap:=0; 37     neck:=inf; 38     while h[0]
      
       -1 do 43       begin 44         j:=edge[i].point; 45         if (edge[i].flow>0) and (h[u]=h[j]+1) then 46         begin 47           cur[u]:=i; 48           pre[j]:=u; 49           neck:=min(neck,edge[i].flow); 50           u:=j; 51           if u=t then 52           begin 53             while u<>0 do 54             begin 55               u:=pre[u]; 56               i:=cur[u]; 57               dec(edge[i].flow,neck); 58               inc(edge[i xor 1].flow,neck); 59             end; 60             sap:=sap+neck; 61           end; 62           break; 63         end; 64         i:=edge[i].next; 65       end; 66       if i=-1 then 67       begin 68         dec(numh[h[u]]); 69         if numh[h[u]]=0 then exit; 70         tmp:=t; 71         i:=p[u]; 72         q:=-1; 73         while i<>-1 do 74         begin 75           j:=edge[i].point; 76           if (edge[i].flow>0) and (h[j]
       
        0 then 87         begin 88           u:=pre[u]; 89           neck:=d[u]; 90         end; 91       end; 92     end; 93   end; 94  95 begin 96   len:=-1; 97   fillchar(p,sizeof(p),255); 98   readln(n); 99   t:=n*n*n+1;100   for i:=1 to n do101   begin102     for j:=1 to n do103     begin104       readln(s);105       for k:=1 to n do106       begin107         inc(m);108         num[i,j,k]:=m;109         if (s[k]='N') and ((i+j+k) mod 2=1) or (s[k]='P') and ((i+j+k) mod 2=0) then110         begin111           add(0,m,inf);112           add(m,0,0);113           add(m,t,1);114           add(t,m,0);115         end116         else if (s[k]='N') and ((i+j+k) mod 2=0) or (s[k]='P') and ((i+j+k) mod 2=1) then117         begin118           add(m,t,inf);119           add(t,m,0);120           add(0,m,1);121           add(m,0,0);122         end123         else if s[k]='?' then124         begin125           add(0,m,1);126           add(m,0,0);127           add(m,t,1);128           add(t,m,0);129         end;130       end;131     end;132     if i<>n then readln;133   end;134   for i:=1 to n do135     for j:=1 to n do136       for k:=1 to n do137         for m:=1 to 6 do138         begin139           x:=i+dx[m];140           y:=j+dy[m];141           z:=k+dz[m];142           if num[x,y,z]>0 then143           begin144             add(num[i,j,k],num[x,y,z],1);145             add(num[x,y,z],num[i,j,k],0);146             inc(sum);147           end;148         end;149   sum:=sum div 2+n*n*n;150   writeln(sum-sap);151 end.