【BZOJ 1976】 [BeiJing2010组队]能量魔方 Cube

1976: [BeiJing2010组队]能量魔方 CubeTime Limit:10 SecMemory Limit:64 MBSubmit:854Solved:290[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

2P? ?? ?? N?

Sample Output

9

HINT

如下状态时，可产生最多的能量。PNNPNPNN【数据规模】10% 的数据N≤3；30% 的数据N≤4；80% 的数据N≤10；100% 的数据N≤40。

最小割。

和【BZOJ 2132】 一样的思路。

只是这道题多了一些已知的格子，那么他对应的点与s/t连inf的边，表示他必须属于s集/t集

#include <iostream>#include <algorithm>#include <cstring>#include <cstdio>#include <cmath>#include <queue>#define M 40*40*40+5#define inf 0x3f3f3f3fusing namespace std;int fx[10][4],c[45][45][45],num[45][45][45],n,tot=1,s,t,h[M],d[M],v[M],cur[M],ans;char S[45][45][45];struct edge{int from,to,cap,flow,ne;}E[200005];void Addedge(int from,int to,int cap){E[++tot]=(edge){from,to,cap,0,h[from]};h[from]=tot;E[++tot]=(edge){to,from,0,0,h[to]};h[to]=tot;}bool bfs(){for (int i=s;i<=t;i++)v[i]=0;v[s]=1;d[s]=0;queue<int> q;q.push(s);while (!q.empty()){int x=q.front();q.pop();for (int i=h[x];i;i=E[i].ne){edge e=E[i];if (!v[e.to]&&e.cap>e.flow){v[e.to]=1;d[e.to]=d[x]+1;q.push(e.to);}}}return v[t];}int dfs(int x,int a){if (x==t||!a)return a;int flow=0;for (int &i=cur[x];i;i=E[i].ne){edge &e=E[i];if (d[e.to]!=d[x]+1) continue;int f=dfs(e.to,min(a,e.cap-e.flow));if (f){flow+=f;a-=f;e.flow+=f;E[i^1].flow-=f;if (!a) break;}}return flow;}int dinic(){int flow=0;while (bfs()){for (int i=s;i<=t;i++)cur[i]=h[i];flow+=dfs(s,inf);}return flow;}void Paint(){for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)c[0][i][j]=(i+j)&1;for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)for (int k=1;k<=n;k++)c[i][j][k]=1^c[i-1][j][k],num[i][j][k]=n*n*(i-1)+n*(j-1)+k;}void Build(){fx[1][1]=fx[3][2]=fx[5][3]=1;fx[2][1]=fx[4][2]=fx[6][3]=-1;for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)for (int k=1;k<=n;k++){int x=num[i][j][k];if (c[i][j][k]){if (S[i][j][k]=='P') Addedge(s,x,inf);if (S[i][j][k]=='N') Addedge(x,t,inf);}else{if (S[i][j][k]=='N') Addedge(s,x,inf);if (S[i][j][k]=='P') Addedge(x,t,inf);}for (int p=1;p<=6;p++){int ni=i+fx[p][1],nj=j+fx[p][2],nk=k+fx[p][3];if (ni<1||nj<1||nk<1||ni>n||nj>n||nk>n) continue;Addedge(x,num[ni][nj][nk],1);ans++;}}ans>>=1;}int main(){scanf("%d",&n);s=0,t=n*n*n+1;for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)scanf("%s",1+S[i][j]);Paint();Build();printf("%d\n",ans-dinic());return 0;}

于是渐渐开始有些伤怀。