[BeiJing2010组队]能量魔方 Cube 【神来一割】★★

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1976

【算法分析】

这题是膜拜了解题报告才会得。

我只想说。。。我被虐到泪流满面

然后我来复述BT的解题报告。

首先，如果用bfs黑白交替染色，会发现每个点只会有一种颜色。（实际上就是到左上角那个点的哈密顿距离的奇偶性）

然后我们把奇点放左边，偶点放右边。

我们再定义：只有正能量的水晶能放出能量，而放出的能量就是它附近的负水晶个数。

这样。我们就可以利用一个最小割模型来求解。

我们想假设所有的点都是P点，并且他能放出最多的能量。（就是他放出和他相邻的格子数的能量）

然后就开始BT了。。。

定义：对于一个割，

如果奇点被割到和源相连的那一边。那么算是P，否则算是N。

如果偶点被割到和汇相连的那一边。那么算是P，否则算是N。

然后对应地。

我们连边S->奇点，容量为该奇点相邻点的个数。

连边偶点->T，容量为该偶点相邻点的个数。（其实除了边界，都是6）

然后对于相邻的奇偶两点，连边 奇点->偶点，容量为2。

这样连的理由是。

如果S->奇点的边成为割边，那么该奇点就变成N了。那么将不再放出能量。所以减去属于他放出的能量。

如果偶点->T的边成为割边，那么该偶点就变成N了。那么也不再放出能量。所以减去属于他放出的能量。

如果奇点->偶点的边成为割边，那么必然（奇点属于S集）（偶点属于T集） 【否则怎么叫割边。。。】

那么就是这个奇点和那个偶点都同时成为了P。那么他们放出的能量都要减1。一共减2。

原因是：本来假设相邻的点都是N，所以当成可以放出全部能量，但是因为相邻的这个不是N。所以大家放出的能量都要减~

所以最后的答案就是：每个点的相邻格子数之和减去最小割。

【其它】

感叹一句：太imba了。

我写的sap再次过不了。。。难道又疵了。。。

改成dinic才过。。。

另外强力膜拜75MS的tracyhenry大神。

【CODE】

#include

#include

#include #include using namespace std;
const int N=40;
const int INF=1000000000;
int n,Sum;
int pos[N][N][N];
char map[N][N][N];
bool odd[N][N][N];
struct edge{int x,y,c;edge *next,*op;};
struct Network_t{
       edge g[1000000],*ls[100000],*cur[100000];
       int vs,vt,d[100000],Flow,Q[100000],e;
      
       void addedge(int x,int y,int c){
            g[++e].x=x; g[e].y=y; g[e].c=c; g[e].next=ls[x]; ls[x]=&g[e]; g[e].op=&g[e+1];
            g[++e].x=y; g[e].y=x; g[e].c=0; g[e].next=ls[y]; ls[y]=&g[e]; g[e].op=&g[e-1];
       }
      
       int dfs(int p,int nf){
           if (p==vt) return nf;
           int tmp,FF=0;
           for (edge *&t=cur[p];t;t=t->next)
             if (t->c && d[t->x]+1==d[t->y] && (tmp=dfs(t->y,min(nf,t->c)))){
               FF+=tmp;
               t->c-=tmp; t->op->c+=tmp;
               if (!(nf-=tmp)) break;
             }
           if (!cur[p]) d[p]=INF;
           return FF;
       }
      
       bool bfs(){
            for (int i=vs;i<=vt;i++){
                d[i]=INF;
                cur[i]=ls[i];
            }
            d[vs]=1; Q[1]=vs;
            for (int st=1,ed=1;d[Q[st]]              for (edge *t=ls[Q[st]];t;t=t->next)
                if (t->c && d[t->y]==INF) d[ Q[++ed]=t->y ]=d[t->x]+1;
            if (d[vt]==INF) return false;
            return true;
       }
      
       void dinic(){
            Flow=0;
            int tmp;
            while (bfs())
              while (tmp=dfs(vs,INF)) Flow+=tmp;
       }
}Network;

bool flag(int x,int y,int z){return (0<=x && xvoid init(){
     scanf("%d",&n);
     int i,j,k,cnt=0;
     char ch;
     for (k=0;k       for (i=0;i         for (j=0;j             ch=getchar();
             while (ch==’ ‘ || ch==’n’) ch=getchar();
             map[k][i][j]=ch;
             pos[k][i][j]=++cnt;
             if (!i && !j) odd[k][i][j]=k%2; else
             if (!i) odd[k][i][j]=!odd[k][i][j-1]; else
             odd[k][i][j]=!odd[k][i-1][j];
         }
     Network.vs=0; Network.vt=++cnt;
     for (k=0;k       for (i=0;i         for (j=0;j             cnt=0;
             if (flag(k-1,i,j)) cnt++;
             if (flag(k+1,i,j)) cnt++;
             if (flag(k,i-1,j)) cnt++;
             if (flag(k,i+1,j)) cnt++;
             if (flag(k,i,j-1)) cnt++;
             if (flag(k,i,j+1)) cnt++;
             Sum+=cnt;
             if (odd[k][i][j]){
               Network.addedge(Network.vs,pos[k][i][j],cnt);
               switch (map[k][i][j]){
                 case ‘P’:Network.addedge(Network.vs,pos[k][i][j],INF); break;
                 case ‘N’:Network.addedge(pos[k][i][j],Network.vt,INF); break;
               }
               if (flag(k-1,i,j)) Network.addedge(pos[k][i][j],pos[k-1][i][j],2);
               if (flag(k+1,i,j)) Network.addedge(pos[k][i][j],pos[k+1][i][j],2);
               if (flag(k,i-1,j)) Network.addedge(pos[k][i][j],pos[k][i-1][j],2);
               if (flag(k,i+1,j)) Network.addedge(pos[k][i][j],pos[k][i+1][j],2);
               if (flag(k,i,j-1)) Network.addedge(pos[k][i][j],pos[k][i][j-1],2);
               if (flag(k,i,j+1)) Network.addedge(pos[k][i][j],pos[k][i][j+1],2);
             }else{
               Network.addedge(pos[k][i][j],Network.vt,cnt);
               switch (map[k][i][j]){
                 case ‘P’:Network.addedge(pos[k][i][j],Network.vt,INF); break;
                 case ‘N’:Network.addedge(Network.vs,pos[k][i][j],INF); break;
               }
             }
         }
}

int main(){
    init();
    Network.dinic();
    printf("%dn",Sum-Network.Flow);
    return 0;
}