终于忙完期末考试了，即将进入愉快的暑假（虽然暑假作业奇多，但好歹终于能有大量时间刷题了）
先把上次新一类最小割留下的一道题目A了复习一下；
题目看起来很复杂，实际上和bzoj2132是同一个类型的
用S集合表示放正能量，T集合表示放负能量（可自行参照上一篇文章）
只是有几个不同点：
有些点是已经确定为S或T集合中的点
选择点属于S或者属于T都是没有收益的
对于未知的问题我们要转化为已知的问题来求解
首先我们来处理2，考虑到割是我们所得不到的收益，
于是我们可以把每个点选择属于S或者属于T产生的收益都当做是个1，
也就是对于每个点i，连接s--->i, i--->t 容量为1；
最后ans=n*n*n（抵消我们之前强加的收益）+图中的边数-mincut;
下面就是1没有解决了，考虑到割是我们所得不到的收益，
所以，对于那些已经确定为S集合中的点（T集合同理），我们只要使
s--->i 容量为inf，也就让这条边一定不成为割边，那么就满足了这个点的确定性；
好了，即使是立体的，依然可以黑白染色划分二分图，所以其余实现细节类似bzoj2132，这里不加赘述。
const inf=;
dx:array[..] of integer=(-,,,,,);
dy:array[..] of integer=(,,-,,,);
dz:array[..] of integer=(,,,,-,);
type node=record
next,flow,point:longint;
end; var edge:array[..] of node;
h,numh,p,cur,d,pre:array[..] of longint;
num:array[..,..,..] of longint;
t,len,i,j,n,k,x,y,z,m,ans,sum:longint;
s:ansistring; function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end; procedure add(x,y,f:longint);
begin
inc(len);
edge[len].point:=y;
edge[len].flow:=f;
edge[len].next:=p[x];
p[x]:=len;
end; function sap:longint;
var u,i,j,q,neck,tmp:longint;
begin
numh[]:=t+;
for i:= to t do
cur[i]:=p[i];
u:=;
sap:=;
neck:=inf;
while h[]<t+ do
begin
d[u]:=neck;
i:=cur[u];
while i<>- do
begin
j:=edge[i].point;
if (edge[i].flow>) and (h[u]=h[j]+) then
begin
cur[u]:=i;
pre[j]:=u;
neck:=min(neck,edge[i].flow);
u:=j;
if u=t then
begin
while u<> do
begin
u:=pre[u];
i:=cur[u];
dec(edge[i].flow,neck);
inc(edge[i xor ].flow,neck);
end;
sap:=sap+neck;
end;
break;
end;
i:=edge[i].next;
end;
if i=- then
begin
dec(numh[h[u]]);
if numh[h[u]]= then exit;
tmp:=t;
i:=p[u];
q:=-;
while i<>- do
begin
j:=edge[i].point;
if (edge[i].flow>) and (h[j]<tmp) then
begin
q:=i;
tmp:=h[j];
end;
i:=edge[i].next;
end;
h[u]:=tmp+;
inc(numh[h[u]]);
cur[u]:=q;
if u<> then
begin
u:=pre[u];
neck:=d[u];
end;
end;
end;
end; begin
len:=-;
fillchar(p,sizeof(p),);
readln(n);
t:=n*n*n+;
for i:= to n do
begin
for j:= to n do
begin
readln(s);
for k:= to n do
begin
inc(m);
num[i,j,k]:=m;
if (s[k]='N') and ((i+j+k) mod =) or (s[k]='P') and ((i+j+k) mod =) then
begin
add(,m,inf);
add(m,,);
add(m,t,);
add(t,m,);
end
else if (s[k]='N') and ((i+j+k) mod =) or (s[k]='P') and ((i+j+k) mod =) then
begin
add(m,t,inf);
add(t,m,);
add(,m,);
add(m,,);
end
else if s[k]='?' then
begin
add(,m,);
add(m,,);
add(m,t,);
add(t,m,);
end;
end;
end;
if i<>n then readln;
end;
for i:= to n do
for j:= to n do
for k:= to n do
for m:= to do
begin
x:=i+dx[m];
y:=j+dy[m];
z:=k+dz[m];
if num[x,y,z]> then
begin
add(num[i,j,k],num[x,y,z],);
add(num[x,y,z],num[i,j,k],);
inc(sum);
end;
end;
sum:=sum div +n*n*n;
writeln(sum-sap);
end.