北京别墅设计网站,做网站的素材和步骤,wordpress 悬浮音乐,自己建设网站平台步骤【BZOJ1976】[BeiJing2010组队]能量魔方 Cube Description 小C 有一个能量魔方#xff0c;这个魔方可神奇了#xff0c;只要按照特定方式#xff0c;放入不同的 能量水晶#xff0c;就可以产生巨大的能量。 能量魔方是一个 N*N*N 的立方体#xff0c;一共用 N3 个空格可以…【BZOJ1976】[BeiJing2010组队]能量魔方 Cube Description 小C 有一个能量魔方这个魔方可神奇了只要按照特定方式放入不同的 能量水晶就可以产生巨大的能量。 能量魔方是一个 N*N*N 的立方体一共用 N3 个空格可以填充能量水晶。 能量水晶有两种 ·一种是正能量水晶(Positive) ·一种是负能量水晶(Negative) 当这个魔方被填满后就会依据填充的能量水晶间的关系产生巨大能量。对 于相邻两(相邻就是拥有同一个面)的两个格子如果这两个格子填充的是一正一 负两种水晶就会产生一单位的能量。而整个魔方的总能量就是这些产生的能 量的总和。 现在小 C 已经在魔方中填充了一些水晶还有一些位置空着。他想知道 如果剩下的空格可以随意填充那么在最优情况下这个魔方可以产生多少能量。 Input 第一行包含一个数N表示魔方的大小。 接下来 N2 行每行N个字符每个字符有三种可能 P表示此方格已经填充了正能量水晶 N表示此方格已经填充了负能量水晶 ?表示此方格待填充。 上述 N*N 行第(i-1)*N1~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];
queueint q;
int dfs(int x,int mf)
{if(xT) return mf;int i,k,tempmf;for(ihead[x];i!-1;inext[i]) if(d[to[i]]d[x]1val[i]){kdfs(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()){uq.front(),q.pop();for(ihead[u];i!-1;inext[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);S0,Ttot1;for(i1;in;i) for(j1;jn;j){scanf(%s,str1);for(k1;kn;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(i1;in;i) for(j1;jn;j) for(k1;kn;k){if(map[i][j][k]1){ab0,cmap[i][j][k];for(l0;l6;l){xidx[l],yjdy[l],zkdz[l];if(xyzxnynzn){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),ansab;}if(map[i][j][k]0){for(l0;l6;l){xidx[l],yjdy[l],zkdz[l];if(xyzxnynznmap[x][y][z]1) ans;}}}while(bfs()) ans-dfs(S,130);printf(%d,ans);return 0;
} 转载于:https://www.cnblogs.com/CQzhangyu/p/7603799.html
