【BZOJ1976】[BeiJing2010組隊]能量魔方 Cube
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
9 HINT
如下狀態時，可產生最多的能量。?
PN?
NP?
NP?
NN?
【數據規模】?
10% 的數據N≤3；?
30% 的數據N≤4；?
80% 的數據N≤10；?
100% 的數據N≤40。?
題解：經典的最小割模型，只不過變成了三維的。先黑白染色，然后黑色的點翻轉源匯，具體方法：
1.S ->i 容量為i周圍已確定的N個數
2.i -> T 容量為i周圍已確定的P個數
上面2條邊要翻轉源匯
3.i <-> j 容量1
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
int n,ans,cnt,tot,S,T;
int dx[]={0,0,0,0,1,-1},dy[]={0,0,1,-1,0,0},dz[]={1,-1,0,0,0,0};
int map[50][50][50],to[2000000],next[2000000],val[2000000],d[100000],head[100000];
char str[50];
queue<int> q;
int dfs(int x,int mf)
{if(x==T) return mf;int i,k,temp=mf;for(i=head[x];i!=-1;i=next[i]) if(d[to[i]]==d[x]+1&&val[i]){k=dfs(to[i],min(temp,val[i]));if(!k) d[to[i]]=0;val[i]-=k,val[i^1]+=k,temp-=k;if(!temp) break;}return mf-temp;
}
int bfs()
{while(!q.empty()) q.pop();memset(d,0,sizeof(d));int i,u;q.push(S),d[S]=1;while(!q.empty()){u=q.front(),q.pop();for(i=head[u];i!=-1;i=next[i]){if(!d[to[i]]&&val[i]){d[to[i]]=d[u]+1;if(to[i]==T) return 1;q.push(to[i]);}}}return 0;
}
inline void add(int a,int b,int c)
{to[cnt]=b,val[cnt]=c,next[cnt]=head[a],head[a]=cnt++;to[cnt]=a,val[cnt]=0,next[cnt]=head[b],head[b]=cnt++;
}
int main()
{int i,j,k,l,x,y,z,a,b,c;scanf("%d",&n);S=0,T=tot=1;for(i=1;i<=n;i++) for(j=1;j<=n;j++){scanf("%s",str+1);for(k=1;k<=n;k++){if(str[k]=='P') map[i][j][k]=1;if(str[k]=='N') map[i][j][k]=0;if(str[k]=='?') map[i][j][k]=++tot;}}memset(head,-1,sizeof(head));for(i=1;i<=n;i++) for(j=1;j<=n;j++) for(k=1;k<=n;k++){if(map[i][j][k]>1){a=b=0,c=map[i][j][k];for(l=0;l<6;l++){x=i+dx[l],y=j+dy[l],z=k+dz[l];if(x&&y&&z&&x<=n&&y<=n&&z<=n){if(map[x][y][z]==0) b++;if(map[x][y][z]==1) a++;if(map[x][y][z]>1&&((i^j^k)&1)) add(c,map[x][y][z],1),add(map[x][y][z],c,1),ans++;}}if((i^j^k)&1) swap(a,b);add(S,c,a),add(c,T,b),ans+=a+b;}if(map[i][j][k]==0){for(l=0;l<6;l++){x=i+dx[l],y=j+dy[l],z=k+dz[l];if(x&&y&&z&&x<=n&&y<=n&&z<=n&&map[x][y][z]==1) ans++;}}}while(bfs()) ans-=dfs(S,1<<30);printf("%d",ans);return 0;
}
轉載于:https://www.cnblogs.com/CQzhangyu/p/7603799.html
總結
以上是生活随笔為你收集整理的【BZOJ1976】[BeiJing2010组队]能量魔方 Cube 最小割的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
