能量魔方

Time Limit: 10 Sec Memory Limit: 64 MB

Description

小C 有一个能量魔方，这个魔方可神奇了，只要按照特定方式，放入不同的 能量水晶，就可以产生巨大的能量。 能量魔方是一个 NNN 的立方体，一共用 N3 个空格可以填充能量水晶。 能量水晶有两种： ·一种是正能量水晶(Positive) ·一种是负能量水晶(Negative) 当这个魔方被填满后，就会依据填充的能量水晶间的关系产生巨大能量。对 于相邻两(相邻就是拥有同一个面)的两个格子，如果这两个格子填充的是一正一 负两种水晶，就会产生一单位的能量。而整个魔方的总能量，就是这些产生的能 量的总和。 现在，小 C 已经在魔方中填充了一些水晶，还有一些位置空着。他想知道， 如果剩下的空格可以随意填充，那么在最优情况下，这个魔方可以产生多少能量。

Input

第一行包含一个数N，表示魔方的大小。 接下来 N2 行，每行N个字符，每个字符有三种可能： P：表示此方格已经填充了正能量水晶； N：表示此方格已经填充了负能量水晶； ?：表示此方格待填充。 上述 N*N 行，第(i-1)N+1~iN 行描述了立方体第 i 层从前到后，从左到右的 状态。且每 N 行间，都有一空行分隔。

Output

仅包含一行一个数，表示魔方最多能产生的能量

Sample Input

2
　P?
　??

??
　N?

Sample Output

9

explain：
　　PN
　　NP
　　
　　NP
　　NN

HINT

n<=40

Main idea

给出一个nnn的矩阵，其中每一个方块可以涂两种颜色，相邻的两个方块如果涂上的颜色不同，就会产生能量。已知了一些方块的颜色，询问最多可以的最多能量。

Solution

发现n<=40，大胆猜测是个网络流。思考过后，发现直接求不好连边，那么我们考虑求出最小损耗，然后用(总收益)-(最小损耗)。

由于相邻的才对答案有贡献，所以我们想到了黑白染色，将所有点划分为两类，那么显然将相邻的点都连一条双向边，权值为1。然后我们考虑如何处理已经规定的点，这时候可以令S集表示1，令T集表示0，将白点的1连向T权值为INF，将S连向黑点的1权值为INF，这样就可以表示不可选了，点权为0则相反。然后跑一遍最小割，计算即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include<bits/stdc++.h>
using namespace std;
#define ID(x,y,z) ((z-1)*n*n + (x-1)*n + y)

const int ONE=70001;
const int TWO=1000001;
const int INF=1073741820;

int n,S,T;
char ch[ONE],c;
int a[45][45][45];
int next[TWO],first[TWO],go[TWO],w[TWO],tot;
int q[2000001],tou,wei;
int Dep[ONE],E[TWO];
int Ans;

int get()
{
    int res=1,Q=1;char c;
    while( (c=getchar())<48 || c>57 )
        if(c=='-')Q=-1;
    res=c-48;
    while( (c=getchar())>=48 && c<=57 )
        res=res*10+c-48;
    return res*Q;
}

void Add(int u,int v,int z)
{
    next[++tot]=first[u];   first[u]=tot;   go[tot]=v;  w[tot]=z;
    next[++tot]=first[v];   first[v]=tot;   go[tot]=u;  w[tot]=0;
}

void Double_Add(int u,int v,int z)
{
    Add(u,v,z);
    Add(v,u,z);
}

int PD(int x,int y,int z)
{
    return (x+y+z)%2;
}

int Bfs()
{
    memset(Dep,0,sizeof(Dep));
    tou=0;  wei=1;  Dep[0]=1; q[1]=0;
    for(int u=0;u<=T-1;u++) E[u]=first[u];
    while(tou<wei)
    {
        int u=q[++tou];
        for(int e=first[u];e;e=next[e])
        {
            int v=go[e];
            if(Dep[v] || !w[e]) continue;
            Dep[v]=Dep[u]+1;
            q[++wei]=v;
        }
    }
    return Dep[T]>0;
}

int Dfs(int u,int Limit)
{
    if(u==T || !Limit) return Limit;
    int flow=0,f;
    for(int &e=E[u];e;e=next[e])
    {
        int v=go[e];
        if(Dep[v]!=Dep[u]+1 || !w[e]) continue;
        f=Dfs(v,min(Limit,w[e]));
        w[e]-=f;
        w[((e-1)^1)+1]+=f;
        Limit-=f;
        flow+=f;
        if(!Limit) break;
    }
    return flow;
}

int main()
{
    cin>>n;

    S=0;    T=n*n*n+1;
    for(int z=1;z<=n;z++)
        for(int x=1;x<=n;x++)
        {
            scanf("%s",ch+1);
            for(int y=1;y<=n;y++)
            {
                if(ch[y]=='?') a[x][y][z]=1;
                if(ch[y]=='P') a[x][y][z]=2;
                if(ch[y]=='N') a[x][y][z]=3;
            }
        }

    for(int z=1;z<=n;z++)
        for(int x=1;x<=n;x++)
            for(int y=1;y<=n;y++)
            {
                if(a[x+1][y][z]) Double_Add(ID(x,y,z),ID(x+1,y,z),1),Ans++;
                if(a[x][y+1][z]) Double_Add(ID(x,y,z),ID(x,y+1,z),1),Ans++;
                if(a[x][y][z+1]) Double_Add(ID(x,y,z),ID(x,y,z+1),1),Ans++;

                if(a[x][y][z]==2)
                {
                    if(PD(x,y,z)) Add(S,ID(x,y,z),INF);
                    else Add(ID(x,y,z),T,INF);
                }

                if(a[x][y][z]==3)
                {
                    if(PD(x,y,z)) Add(ID(x,y,z),T,INF);
                    else Add(S,ID(x,y,z),INF);
                }
            }

    while(Bfs())
    {
        Ans-=Dfs(S,INF);
    }

    printf("%d",Ans);
}