dango

Hdu 3231 Box Relations

题目描述：

    原题地址：http://acm.hdu.edu.cn/showproblem.php?pid=3231

    给定一些正方体的关系，要求一组符合这些关系的正方体坐标，如果不存在符合条件的正方体坐标，IMPOSSIBLE。(Special Judge)

题目分析：

    首先把正方体这个立体问题拆分成X，Y，Z三个维度上的的平面问题。三个维度上的平面问题处理完了，正方体问题也就处理完了。

    首先想到了差分约束系统，但是我的SPFA呃，TLE了……（求一个不TLE的差分约束系统标程……）

    上网搜索了一个大牛的文，说只需要拓补排序就可以了，完全不需要差分约束。

    再想一想，此题如果用差分约束系统来做，所有边权都是-1。其实不如更直观地进行构图，例如a<b，那么就构图map[a][b] = 1，也就是不妨看做a到b的边权为1。其实进行一下拓补排序，根据点的拓补排序的结果就可以直接作为答案输出，如果拓补排序失败也就是IMPOSSIBLE。

代码：

hdu3231
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#define MAXN 2010
#define MAXR 500000
#define MAX 999999

typedef struct edges{
    int v,w,next;
}edge;

int N, R;
edge edge_X[MAXR], edge_Y[MAXR], edge_Z[MAXR];
int s_X[MAXN], s_Y[MAXN], s_Z[MAXN];
int index_X[MAXN], index_Y[MAXN], index_Z[MAXN];
int degree_X[MAXN], degree_Y[MAXN], degree_Z[MAXN];

void Add(struct edges e[], int start, int end, int index[], int degree[], int &tot){
    e[tot].v = end;
    e[tot].next = index[start];
    index[start] = tot++;
    degree[end]++;
}

bool init(){
    int i, totx, toty, totz; 
    scanf("%d%d", &N, &R);
    if (N == 0 && R == 0) return false;
    memset(index_X, 255, sizeof(*index_X)*MAXN); //-1 indicates end of link
    memset(index_Y, 255, sizeof(*index_Y)*MAXN); 
    memset(index_Z, 255, sizeof(*index_Z)*MAXN); 
    memset(degree_X, 0, sizeof(*degree_X)*MAXN);
    memset(degree_Y, 0, sizeof(*degree_Y)*MAXN);
    memset(degree_Z, 0, sizeof(*degree_Z)*MAXN);
    totx = toty = totz = 0;
    
    for (i=1; i<=N; i++){
        // node 0是超级汇点，最大的点。值为0
        Add(edge_X, 0, i, index_X, degree_X, totx);         //x1 of n-th Cube
        Add(edge_Y, 0, i, index_Y, degree_Y, toty);
        Add(edge_Z, 0, i, index_Z, degree_Z, totz);
        Add(edge_X, i, i+N, index_X, degree_X, totx);
        Add(edge_Y, i, i+N, index_Y, degree_Y, toty);
        Add(edge_Z, i, i+N, index_Z, degree_Z, totz);
    }
    for (i=1; i<=R; i++){
        char t[10];
        int  A, B;
        scanf("%s%d%d", t, &A, &B);
        if (t[0] == 'I'){
            Add(edge_X, A, B+N, index_X, degree_X, totx);        //x1(A) < x1(B)
            Add(edge_X, B, A+N, index_X, degree_X, totx);        //x2(A) > x1(B) or x1(B) < x2(A)
            Add(edge_Y, A, B+N, index_Y, degree_Y, toty);
            Add(edge_Y, B, A+N, index_Y, degree_Y, toty);
            Add(edge_Z, A, B+N, index_Z, degree_Z, totz);
            Add(edge_Z, B, A+N, index_Z, degree_Z, totz);
        }
        if (t[0] == 'X')
            Add(edge_X, A+N, B, index_X, degree_X, totx);    //x2(A) < x1(B)
        if (t[0] == 'Y')
            Add(edge_Y, A+N, B, index_Y, degree_Y, toty);    //y2(A) < y1(B)
        if (t[0] == 'Z')
            Add(edge_Z, A+N, B, index_Z, degree_Z, totz);    //z2(A) < z1(B)    
    }
    return true;
}

bool NonPreFirstTopSort(edge e[], int index[], int degree[], int n, int s[]){
    int i, count(0), head(0), tail(1);
    int Q[MAXN];
    
    Q[0] = 0;
    
    while (head != tail){
        s[Q[head]] = count++;
        i = index[Q[head]];
        while (i != -1){
            if (--degree[e[i].v] == 0) Q[tail++] = e[i].v;
            i = e[i].next;
        }
        ++head;
    }
    
    if (count < n) return false;
    else return true;
}

int main(){
    int Cases = 0, i;
    while (init() && ++Cases){
        bool flag;
        flag = NonPreFirstTopSort(edge_X, index_X, degree_X, N*2 + 1, s_X);
        if (flag) flag = NonPreFirstTopSort(edge_Y, index_Y, degree_Y, N*2 + 1, s_Y);
        if (flag) flag = NonPreFirstTopSort(edge_Z, index_Z, degree_Z, N*2 + 1, s_Z);
        if (flag){
            printf("Case %d: POSSIBLE\n", Cases);
            for (i=1; i<=N; i++)
                printf("%d %d %d %d %d %d\n", s_X[i], s_Y[i], s_Z[i], s_X[i+N],  s_Y[i+N], s_Z[i+N]);
            printf("\n");
            
        }
        else
            printf("Case %d: IMPOSSIBLE\n\n", Cases);
    }
    //system("pause");
    return 0;
}