poj1022:Packing Unit 4D Cubes四維魔方的題意和題解

囧，題意看起來 很復雜，故幾乎沒什麼人提交，其實只要看懂了題目的意思再簡單不過了，，，這不，因為英語不好花了很久才看懂題意，稍微解釋一下吧：
定義一個四維的魔方，每個四維的魔方有八個面（類比3維的魔方有六個面），每個面是一個3維的東西（類比3維的魔方的每個面是2維的平面）。
然後要把n個四維的魔方包裝起來，因為是四維的，所以有四根坐標軸，每個魔方給出9個數據，第一個是此魔方的標識，然後1，2個表示在沿著第一根軸的前面和後面的用膠水
粘貼起來的魔方的編號，沒有便為0。然後要你計算這n個四維魔方組裝成的EER的“體積”（體積是相對與四維而言的）。理解了題意就簡單了，直接由3維的外推到4維，3維裡怎
麼做在四維裡就怎麼做。如：體積等於每個坐標軸的距離乘起來。反正按3維的思考方法來就是了。
然後有兩個判斷：1是如果x在y上面那y必在x下面，如不成立則不存在。
                        2是最後只能組裝城一個產品，不是多個，dfs求連通分量即可
AC代碼如下：（第一次以為魔方的標識符在1到n之間，其實不是，搞得re了幾次）

[cpp] 
# include <stdio.h> 
# include <string.h> 
# include <stdlib.h> 
# define get(x) (((x-1)&((1 << 31) - 2)+((x-1)&1)^1)+1) 
# define DEBUG 
 
int s[111][11]; 
int use[111]; 
int check[111]; 
int re[111]; 
 
int go(int x, int n) { 
    for (int i = 1; i <= n; ++ i){ 
        if(re[i] == x) return i; 
    } 
} 
 
int check1(int n) { 
    for (int i = 1; i <= n; ++ i) { 
        for (int j = 1; j <= 8; ++ j) { 
            if (s[i][j] && s[go(s[i][j], n)][get(j)] != re[i]) return 1; 
        } 
    } 
    return 0; 
} 
 
int dfs(int x, int n) { 
    if(check[x]) return 0; 
    check[x] = 1; 
    for (int i = 1; i <= 8; ++ i) { 
        if(s[x][i]) { 
            int t = go(s[x][i], n); 
            use[t] = 1; 
            dfs(t,n); 
        } 
    } 
    return 0; 
} 
 
int check2(int n, int x) { 
    dfs(x,n); 
    for (int i = 1; i <= n; ++ i) { 
        if (!use[i]) return 1; 
    } 
    return 0; 
} 
 
int getAns(int n) { 
    int x[5]; 
    memset(x, 0, sizeof(x)); 
    for (int i = 1; i <= n; ++ i) { 
        for (int j = 1; j <= 8; ++ j) { 
            if(s[i][j]) { 
                ++ x[(j + 1) >> 1]; 
            } 
        } 
    } 
    int su = 1; 
    for (int i = 1; i <= 4; ++ i) { 
        su *= (x[i] >> 1) + 1; 
    } 
    printf ("%d\n", su); 
    return 0; 
} 
 
int main () { 
    int ts; 
    for (scanf("%d", &ts); ts; -- ts) { 
        int n; 
        scanf("%d", &n); 
        memset(s, 0, sizeof(s)); 
        memset(use, 0, sizeof(use)); 
        memset(check, 0, sizeof(check)); 
        memset(re, 0, sizeof(re)); 
        int t; 
        for (int i = 1; i <= n; ++ i) { 
            scanf("%d", &t); 
            re[i] = t; 
            s[i][0] = t; 
            for (int j = 1; j <= 8; ++ j) { 
                scanf("%d", &s[i][j]); 
            } 
        }   www.2cto.com
        //printf ("%d %d", check1(n), check2(n, t)); 
        if(check1(n) || check2(n, 1)) { 
            printf ("Inconsistent\n"); 
        } 
        else { 
            getAns(n); 
        } 
    } 
 
 
 
    return 0; 
}