【BZOJ-1976】能量魔方Cube 最小割 + 黑白染色

1976: [BeiJing2010组队]能量魔方 Cube

Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 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

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
",tot-ans);
    return 0;
}

用了BeiYu的黑科技，流同步什么的..因为OJ的原因WA了两次QAQ