1976: [BeiJing2010组队]能量魔方 Cube
Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 879 Solved: 304
[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?
??
P?
??
??
N?
Sample Output
9
HINT
如下状态时，可产生最多的能量。
PN
NP
NP
NN
【数据规模】
10% 的数据N≤3；
30% 的数据N≤4；
80% 的数据N≤10；
100% 的数据N≤40。
Source
题解：
最小割，思路很好。
我们可以发现这道题与之前的几道题略有不同，这里是两个格子所属类别不同时获得某种收益。所以我们单纯地按照两个类别建立源点和汇点，连边求最小割就行不通了。
那怎么办呢？能不能还用最小割解决呢？
答案当然是能，不然我第一行为什么会写“最小割”三个字…2333
我们考虑能不能有一种方案，让任意两个相邻格子颜色都不同。当然是可以的，只要对一个n*n*n的立方体黑白染色就可以了。对于黑色，我们用s表示positive，t表示negative；相反地，对于白色，用s表示negative，t表示positive。这样，我们就把所属与不同类别转化为所属相同类别。是不是很机智啊！
但是题目中是有限定条件的，也就是有些点的类别是固定的，这也很好办。比如说对于黑色，如果已经确定为positive，连边(s,i,inf)；如果已经确定为negative，连边(i,t,inf)。因为inf的边一定不会成为割，也就保证了i节点一定属于s割或者t割，即保证了它是positive或者negative。白色同理。
然后对于任意两个相邻格子i和j，连边（i,j,1）（j,i,1）。
最后跑一次最小割，从总收益中减去最小割即为答案。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAXN 64020
#define INF 1e9
struct node
{
int begin,end,value,next;
}edge[*MAXN];
int cnt,Head[MAXN],S,T,dis[MAXN],q[MAXN],n,cur[MAXN]; void addedge(int bb,int ee,int vv)
{
edge[++cnt].begin=bb;edge[cnt].end=ee;edge[cnt].value=vv;edge[cnt].next=Head[bb];Head[bb]=cnt;
}
void addedge1(int bb,int ee,int vv)
{
addedge(bb,ee,vv);addedge(ee,bb,);
}
int xyz(int x,int y,int z){return (x-)*n*n+(y-)*n+z;}
int BFS()
{
int head,tail,i,u,v;
head=;tail=;q[tail]=S;
memset(dis,-,sizeof(dis));dis[S]=;//0打成-1了。。。改死我了。。。
while(head!=tail)
{
head++;if(head==)head=;
u=q[head];
for(i=Head[u];i!=-;i=edge[i].next)
{
v=edge[i].end;
if(edge[i].value>&&dis[v]<)
{
dis[v]=dis[u]+;
tail++;if(tail==)tail=;
q[tail]=v;
}
}
}
if(dis[T]<=)return ;
else return ;
}
int DFS(int u,int minflow)
{
int used=,ans=,i,v;
if(u==T)return minflow;
for(i=Head[u];i!=-;i=edge[i].next)
{
v=edge[i].end;
if(edge[i].value>&&dis[v]==dis[u]+)
{
ans=minflow-used;
ans=DFS(v,min(ans,edge[i].value));
edge[i].value-=ans;
edge[i^].value+=ans;
used+=ans;
if(used==minflow)return minflow;
}
}
if(used==)dis[u]=-;
return used;
}
int Dinic()
{
int maxflow=,ans=,i;
while(BFS()){for(i=;i<=T;i++)cur[i]=Head[i];ans=DFS(S,INF);if(ans==)break;maxflow+=ans;}
return maxflow;
}
int main()
{
int i,j,k,XYZ,ans;
char ch;
scanf("%d",&n);
S=n*n*n+;T=S+;//S代表和正能量水晶连,T代表和负能量水晶连.
memset(Head,-,sizeof(Head));cnt=;
for(i=;i<=n;i++)
{
for(j=;j<=n;j++)
{
for(k=;k<=n;k++)
{
if(i!=n)addedge1(xyz(i,j,k),xyz(i+,j,k),);
if(j!=n)addedge1(xyz(i,j,k),xyz(i,j+,k),);
if(k!=n)addedge1(xyz(i,j,k),xyz(i,j,k+),);
if(i!=)addedge1(xyz(i,j,k),xyz(i-,j,k),);
if(j!=)addedge1(xyz(i,j,k),xyz(i,j-,k),);
if(k!=)addedge1(xyz(i,j,k),xyz(i,j,k-),);
}
}
}
for(i=;i<=n;i++)
{
for(j=;j<=n;j++)
{
scanf("\n");
for(k=;k<=n;k++)
{
scanf("%c",&ch);
XYZ=xyz(i,j,k);
if((i+j+k)%==)//黑白染色.
{
if(ch=='P')addedge1(S,XYZ,INF);
else if(ch=='N')addedge1(XYZ,T,INF);
//else addedge1(S,XYZ,INF);
}
else
{
if(ch=='P')addedge1(XYZ,T,INF);
else if(ch=='N')addedge1(S,XYZ,INF);
//else addedge1(XYZ,T,INF);
}
}
}
if(i!=n)scanf("\n");
}
ans=Dinic();
printf("%d",*n*n*(n-)-ans);
fclose(stdin);
fclose(stdout);
return ;
// while(1) getchar();
//getchar();
}