【BZOJ1976】能量魔方 [最小割]

能量魔方

Time Limit: 10 Sec Memory Limit: 64 MB
[Submit][Status][Discuss]

Description

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

Input

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

Output

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

Sample Input

　　2
　　P?
　　??

　　
　　??
　　N?

Sample Output

　　explain：
　　PN
　　NP
　　
　　NP
　　NN

HINT

　　n<=40

Main idea

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

Solution

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

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

Code

  1 #include<iostream>  
  2 #include<algorithm>  
  3 #include<cstdio>  
  4 #include<cstring>  
  5 #include<cstdlib>  
  6 #include<cmath>  
  7 using namespace std;  
  8 #define ID(x,y,z) ((z-1)*n*n + (x-1)*n + y)
  9  
 10 const int ONE=70001;
 11 const int TWO=1000001;
 12 const int INF=1073741820;
 13  
 14 int n,S,T;
 15 char ch[ONE],c;
 16 int a[45][45][45];
 17 int next[TWO],first[TWO],go[TWO],w[TWO],tot;
 18 int q[2000001],tou,wei;
 19 int Dep[ONE],E[TWO];
 20 int Ans;
 21  
 22 int get() 
 23 {    
 24         int res=1,Q=1;char c;    
 25         while( (c=getchar())<48 || c>57 ) 
 26         if(c=='-')Q=-1; 
 27         res=c-48;     
 28         while( (c=getchar())>=48 && c<=57 )    
 29         res=res*10+c-48;    
 30         return res*Q;    
 31 }
 32  
 33 void Add(int u,int v,int z)
 34 {
 35         next[++tot]=first[u];   first[u]=tot;   go[tot]=v;  w[tot]=z;
 36         next[++tot]=first[v];   first[v]=tot;   go[tot]=u;  w[tot]=0;
 37 }
 38  
 39 void Double_Add(int u,int v,int z)
 40 {
 41         Add(u,v,z);
 42         Add(v,u,z);
 43 }
 44  
 45 int PD(int x,int y,int z)
 46 {
 47         return (x+y+z)%2;   
 48 }
 49  
 50 int Bfs()
 51 {
 52         memset(Dep,0,sizeof(Dep));
 53         tou=0;  wei=1;  Dep[0]=1; q[1]=0;
 54         for(int u=0;u<=T-1;u++) E[u]=first[u];
 55         while(tou<wei)
 56         {
 57             int u=q[++tou];
 58             for(int e=first[u];e;e=next[e])
 59             {
 60                 int v=go[e];
 61                 if(Dep[v] || !w[e]) continue;
 62                 Dep[v]=Dep[u]+1;
 63                 q[++wei]=v;
 64             }
 65         }
 66         return Dep[T]>0;
 67 }
 68  
 69 int Dfs(int u,int Limit)
 70 {
 71         if(u==T || !Limit) return Limit;
 72         int flow=0,f;
 73         for(int &e=E[u];e;e=next[e])
 74         {
 75             int v=go[e];
 76             if(Dep[v]!=Dep[u]+1 || !w[e]) continue;
 77             f=Dfs(v,min(Limit,w[e]));
 78             w[e]-=f;
 79             w[((e-1)^1)+1]+=f;
 80             Limit-=f;
 81             flow+=f;
 82             if(!Limit) break;
 83         }
 84         return flow;
 85 }
 86  
 87 int main()
 88 {
 89         cin>>n;
 90          
 91         S=0;    T=n*n*n+1;
 92         for(int z=1;z<=n;z++)
 93         for(int x=1;x<=n;x++)
 94         {
 95             scanf("%s",ch+1);
 96             for(int y=1;y<=n;y++)
 97             {
 98                 if(ch[y]=='?') a[x][y][z]=1;
 99                 if(ch[y]=='P') a[x][y][z]=2;
100                 if(ch[y]=='N') a[x][y][z]=3;
101             }
102         }
103          
104         for(int z=1;z<=n;z++)
105         for(int x=1;x<=n;x++)
106         for(int y=1;y<=n;y++)
107         {
108             if(a[x+1][y][z]) Double_Add(ID(x,y,z),ID(x+1,y,z),1),Ans++;
109             if(a[x][y+1][z]) Double_Add(ID(x,y,z),ID(x,y+1,z),1),Ans++;
110             if(a[x][y][z+1]) Double_Add(ID(x,y,z),ID(x,y,z+1),1),Ans++;
111              
112             if(a[x][y][z]==2)
113             {
114                 if(PD(x,y,z)) Add(S,ID(x,y,z),INF);
115                 else Add(ID(x,y,z),T,INF);
116             }
117          
118             if(a[x][y][z]==3)
119             {
120                 if(PD(x,y,z)) Add(ID(x,y,z),T,INF);
121                 else Add(S,ID(x,y,z),INF);
122             }
123         }
124          
125         while(Bfs())
126         {
127             Ans-=Dfs(S,INF);
128         }
129          
130         printf("%d",Ans);
131 }

View Code