Bzoj 1976: [BeiJing2010组队]能量魔方 Cube 最小割,最大流

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

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

题解：

最小割，思路很好。

我们可以发现这道题与之前的几道题略有不同，这里是两个格子所属类别不同时获得某种收益。所以我们单纯地按照两个类别建立源点和汇点，连边求最小割就行不通了。

那怎么办呢？能不能还用最小割解决呢？

答案当然是能，不然我第一行为什么会写“最小割”三个字…2333

我们考虑能不能有一种方案，让任意两个相邻格子颜色都不同。当然是可以的，只要对一个n*n*n的立方体黑白染色就可以了。对于黑色，我们用s表示positive，t表示negative；相反地，对于白色，用s表示negative，t表示positive。这样，我们就把所属与不同类别转化为所属相同类别。是不是很机智啊！

但是题目中是有限定条件的，也就是有些点的类别是固定的，这也很好办。比如说对于黑色，如果已经确定为positive，连边(s,i,inf)；如果已经确定为negative，连边(i,t,inf)。因为inf的边一定不会成为割，也就保证了i节点一定属于s割或者t割，即保证了它是positive或者negative。白色同理。

然后对于任意两个相邻格子i和j，连边（i,j,1）（j,i,1）。

最后跑一次最小割，从总收益中减去最小割即为答案。

摘自http://doc.okbase.net/AaronGZK/archive/196829.html

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstdlib>
  4 #include<cstring>
  5 #include<cmath>
  6 #include<algorithm>
  7 using namespace std;
  8 #define MAXN 64020
  9 #define INF 1e9
 10 struct node
 11 {
 12     int begin,end,value,next;
 13 }edge[14*MAXN];
 14 int cnt,Head[MAXN],S,T,dis[MAXN],q[MAXN],n,cur[MAXN];
 15  
 16  
 17  
 18 void addedge(int bb,int ee,int vv)
 19 {
 20     edge[++cnt].begin=bb;edge[cnt].end=ee;edge[cnt].value=vv;edge[cnt].next=Head[bb];Head[bb]=cnt;
 21 }
 22 void addedge1(int bb,int ee,int vv)
 23 {
 24     addedge(bb,ee,vv);addedge(ee,bb,0);
 25 }
 26 int xyz(int x,int y,int z){return (x-1)*n*n+(y-1)*n+z;}
 27 int BFS()
 28 {
 29     int head,tail,i,u,v;
 30     head=0;tail=1;q[tail]=S;
 31     memset(dis,-1,sizeof(dis));dis[S]=0;//0打成-1了。。。改死我了。。。
 32     while(head!=tail)
 33     {
 34         head++;if(head==64010)head=0;
 35         u=q[head];
 36         for(i=Head[u];i!=-1;i=edge[i].next)
 37         {
 38             v=edge[i].end;
 39             if(edge[i].value>0&&dis[v]<0)
 40             {
 41                 dis[v]=dis[u]+1;
 42                 tail++;if(tail==64010)tail=0;
 43                 q[tail]=v;
 44             }
 45         }
 46     }
 47     if(dis[T]<=0)return 0;
 48     else return 1;
 49 }
 50 int DFS(int u,int minflow)
 51 {
 52     int used=0,ans=0,i,v;
 53     if(u==T)return minflow;
 54     for(i=Head[u];i!=-1;i=edge[i].next)
 55     {
 56         v=edge[i].end;
 57         if(edge[i].value>0&&dis[v]==dis[u]+1)
 58         {
 59             ans=minflow-used;
 60             ans=DFS(v,min(ans,edge[i].value));
 61             edge[i].value-=ans;
 62             edge[i^1].value+=ans;
 63             used+=ans;
 64             if(used==minflow)return minflow;
 65         }
 66     }
 67     if(used==0)dis[u]=-1;
 68     return used;
 69 }
 70 int Dinic()
 71 {
 72     int maxflow=0,ans=0,i;
 73     while(BFS()){for(i=1;i<=T;i++)cur[i]=Head[i];ans=DFS(S,INF);if(ans==0)break;maxflow+=ans;}
 74     return maxflow;
 75 }
 76 int main()
 77 {
 78     int i,j,k,XYZ,ans;
 79     char ch;
 80     scanf("%d",&n);
 81     S=n*n*n+1;T=S+1;//S代表和正能量水晶连,T代表和负能量水晶连.
 82     memset(Head,-1,sizeof(Head));cnt=1;
 83     for(i=1;i<=n;i++)
 84     {
 85         for(j=1;j<=n;j++)
 86         {
 87             for(k=1;k<=n;k++)
 88             {
 89                if(i!=n)addedge1(xyz(i,j,k),xyz(i+1,j,k),1);
 90                if(j!=n)addedge1(xyz(i,j,k),xyz(i,j+1,k),1);
 91                if(k!=n)addedge1(xyz(i,j,k),xyz(i,j,k+1),1);
 92                if(i!=1)addedge1(xyz(i,j,k),xyz(i-1,j,k),1);
 93                if(j!=1)addedge1(xyz(i,j,k),xyz(i,j-1,k),1);
 94                if(k!=1)addedge1(xyz(i,j,k),xyz(i,j,k-1),1);
 95             }
 96         }
 97     }
 98     for(i=1;i<=n;i++)
 99     {
100         for(j=1;j<=n;j++)
101         {
102             scanf("
");
103             for(k=1;k<=n;k++)
104             {
105                 scanf("%c",&ch);
106                 XYZ=xyz(i,j,k);
107                 if((i+j+k)%2==0)//黑白染色.
108                 {
109                     if(ch=='P')addedge1(S,XYZ,INF);
110                     else if(ch=='N')addedge1(XYZ,T,INF);
111                     //else addedge1(S,XYZ,INF);
112                 }
113                 else
114                 {
115                     if(ch=='P')addedge1(XYZ,T,INF);
116                     else if(ch=='N')addedge1(S,XYZ,INF);
117                     //else addedge1(XYZ,T,INF);
118                 }
119             }
120         }
121         if(i!=n)scanf("
");
122     }
123     ans=Dinic();
124     printf("%d",3*n*n*(n-1)-ans);
125     fclose(stdin);
126     fclose(stdout);
127     return 0;
128   // while(1) getchar();
129    //getchar();
130 }