1976: [BeiJing2010组队]能量魔方 Cube
Time Limit: 10 Sec Memory Limit: 64 MBSubmit: 884 Solved: 307[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
9
HINT
如下状态时，可产生最多的能量。 PN NP NP NN 【数据规模】 10% 的数据N≤3； 30% 的数据N≤4； 80% 的数据N≤10； 100% 的数据N≤40。
Source
Solution
最小割
•
对水晶块黑白染色
•相邻的水晶之间连容量为1的边
•对于黑色，与 S 联通表示正能量，与 P 联通表示负能量，对于白色则相反
•确定的水晶向 S 或 T 连inf边
•同样最后将总和减去最小割即可
Code
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<queue>
using namespace std;
int read()
{
int x=
0,f=
1;
char ch=
getchar();
while (ch<
'0' || ch>
'9') {
if (ch==
'-') f=-
1; ch=
getchar();}
while (ch>=
'0' && ch<=
'9') {x=x*
10+ch-
'0'; ch=
getchar();}
return x*
f;
}
int N;
#define MAXM 2000100
#define MAXN 100
#define INF 0x7fffffff
struct EdgeNode{
int next,to,cap;}edge[MAXM];
int head[MAXN*MAXN*MAXN],cnt=
1;
void add(
int u,
int v,
int w) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v; edge[cnt].cap=
w;}
void insert(
int u,
int v,
int w) {add(u,v,w); add(v,u,
0);}
int h[MAXN*MAXN*MAXN],cur[MAXN*MAXN*
MAXN],S,T;
bool bfs()
{
queue<
int>
q;
for (
int i=S; i<=T; i++) h[i]=-
1;
h[S]=
1; q.push(S);
while (!
q.empty())
{
int now=
q.front(); q.pop();
for (
int i=head[now]; i; i=
edge[i].next)
if (h[edge[i].to]==-
1 &&
edge[i].cap)
h[edge[i].to]=h[now]+
1,q.push(edge[i].to);
}
return h[T]!=-
1;
}
int dfs(
int loc,
int low)
{
if (loc==T)
return low;
int used=
0,w;
for (
int i=cur[loc]; i; i=
edge[i].next)
if (edge[i].cap && h[edge[i].to]==h[loc]+
1)
{
w=dfs(edge[i].to,min(edge[i].cap,low-
used));
edge[i].cap-=w; edge[i^
1].cap+=w; used+=
w;
if (used==low)
return low;
if (edge[i].to) cur[loc]=
i;
}
if (!used) h[loc]=-
1;
return used;
}
int Dinic()
{
int tmp=
0;
while (bfs())
{
for (
int i=S; i<=T; i++) cur[i]=
head[i];
tmp+=
dfs(S,INF);
}
return tmp;
}
int id[MAXN][MAXN][MAXN],tot,ans;
char cube[MAXN][MAXN][MAXN];
void BuildGraph()
{
S=
0,T=N*N*N+
1;
int ID=
0;
for (
int i=
1; i<=N; i++
)
for (
int j=
1; j<=N; j++
)
for (
int k=
1; k<=N; k++
)
id[i][j][k]=++
ID;
for (
int i=
1; i<=N; i++
)
for (
int j=
1; j<=N; j++
)
for (
int k=
1; k<=N; k++
)
{
if (i<N) insert(id[i][j][k],id[i+
1][j][k],
1),insert(id[i+
1][j][k],id[i][j][k],
1);
if (j<N) insert(id[i][j][k],id[i][j+
1][k],
1),insert(id[i][j+
1][k],id[i][j][k],
1);
if (k<N) insert(id[i][j][k],id[i][j][k+
1],
1),insert(id[i][j][k+
1],id[i][j][k],
1);
}
for (
int i=
1; i<=N; i++
)
for (
int j=
1; j<=N; j++
)
for (
int k=
1; k<=N; k++
)
{
if ((i+j+k)%
2)
{
if (cube[i][j][k]==
'P') insert(S,id[i][j][k],INF);
if (cube[i][j][k]==
'N') insert(id[i][j][k],T,INF);
}
else
{
if (cube[i][j][k]==
'P') insert(id[i][j][k],T,INF);
if (cube[i][j][k]==
'N') insert(S,id[i][j][k],INF);
}
}
tot=
3*N*N*(N-
1);
}
int main()
{
//ios::sync_with_stdio(false);
N=
read();
char p;
for (
int i=
1; i<=N; i++
)
{
for (
int j=
1; j<=N; j++
)
for (
int k=
1; k<=N; k++
)
{
cin>>
p;
if (p==
'P') cube[i][j][k]=
'P';
if (p==
'?') cube[i][j][k]=
'?';
if (p==
'N') cube[i][j][k]=
'N';
}
}
BuildGraph();
ans=
Dinic();
printf("%d\n",tot-
ans);
return 0;
}
用了BeiYu的黑科技，流同步什么的..因为OJ的原因WA了两次QAQ
转载于:https://www.cnblogs.com/DaD3zZ-Beyonder/p/5679319.html
相关资源：DirectX修复工具V4.0增强版
