首页 > ACM题库 > HDU-杭电 > HDU 3231-Box Relations-拓扑排序-[解题报告]HOJ
2014
03-09

HDU 3231-Box Relations-拓扑排序-[解题报告]HOJ

Box Relations

问题描述 :

There are n boxes C1, C2, …, Cn in 3D space. The edges of the boxes are parallel to the x, y or z-axis. We provide some relations of the boxes, and your task is to construct a set of boxes satisfying all these relations.

There are four kinds of relations (1 <= i,j <= n, i is different from j):

  • I i j: The intersection volume of Ci and Cj is positive.
  • X i j: The intersection volume is zero, and any point inside Ci has smaller x-coordinate than any point inside Cj.
  • Y i j: The intersection volume is zero, and any point inside Ci has smaller y-coordinate than any point inside Cj.
  • Z i j: The intersection volume is zero, and any point inside Ci has smaller z-coordinate than any point inside Cj.

.

输入:

There will be at most 30 test cases. Each case begins with a line containing two integers n (1 <= n <= 1,000) and R (0 <= R <= 100,000), the number of boxes and the number of relations. Each of the following R lines describes a relation, written in the format above. The last test case is followed by n=R=0, which should not be processed.

输出:

There will be at most 30 test cases. Each case begins with a line containing two integers n (1 <= n <= 1,000) and R (0 <= R <= 100,000), the number of boxes and the number of relations. Each of the following R lines describes a relation, written in the format above. The last test case is followed by n=R=0, which should not be processed.

样例输入:

3 2
I 1 2
X 2 3
3 3
Z 1 2
Z 2 3
Z 3 1
1 0
0 0

样例输出:

Case 1: POSSIBLE
0 0 0 2 2 2
1 1 1 3 3 3
8 8 8 9 9 9

Case 2: IMPOSSIBLE

Case 3: POSSIBLE
0 0 0 1 1 1

题目链接:Click here~~

题意:

在三维空间内,有n个长方体,棱都与坐标轴平行。给出一些关系,问是否可能,若可能,输出其中的一种。

关系有两种:

1、某两个长方体相交。

2、某个长方体的所有点的某一维的坐标完全小于另一个长方体的任意一点。

解题思路:

首先,对于棱与坐标轴平行的长方体,在某一维中,它里面的点可以看做包含在长方体的两个平面内,且点的坐标正好在两个平面的坐标的区间内。

而题目让我们所求的,正是坐标区间,于是我们可以求平面的坐标来得到。

然后,考虑相交的情况,我们可以得出:若某两个长方体相交,当且仅当每一维中,其中的一个长方体的面插进了另一个长方体的内部。

Box Relations

我们以 y 轴为例,画出上图,题中的信息只给出了A和B相交,但是我们不知道谁是A,谁是B,

所以我们只能得到一些与A、B无关的关系:A1<B2、B1<A2,即一个长方体的左面一定小于另一个长方体的右面。

于是我们可以根据这些偏序关系,把长方体的6个面抽象成6个点,对三维分别作拓扑排序,其中每一维只与2个面有关。

#include <queue>
#include <stdio.h>
#include <string.h>
using namespace std;
#define N 2005

struct T
{
    int v,next;
}E[3][N*100];

struct TT
{
    int head,rd,dep;
}V[3][N];

int top[3],ans,n,m;

void Add_Edge(int k,int u,int v)
{
    E[k][top[k]].v = v;
    E[k][top[k]].next = V[k][u].head;
    V[k][u].head = top[k]++;
    ++V[k][v].rd;
}

bool Top_Sort(int k)
{
    queue<int> Q;
    for(int i=1;i<=n;i++)
        if(V[k][i].rd == 0)
            Q.push(i);
    int cnt = 0;
    while(!Q.empty())
    {
        ++cnt;
        int p = Q.front();
        for(int i=V[k][p].head;i!=NULL;i=E[k][i].next)
        {
            int q = E[k][i].v;
            --V[k][q].rd;
            if(V[k][q].rd == 0)
            {
                Q.push(q);
                V[k][q].dep = V[k][p].dep + 1;
            }
        }
        Q.pop();
    }
    return cnt == n;
}
int main()
{
    int u,v,nn,ncase=0;
    char cmd;
    while(~scanf("%d%d%*c",&nn,&m),nn)
    {
        memset(V,0,sizeof(V));
        top[0] = top[1] = top[2] = 1;
        n = 2*nn;
        for(int k=0;k<3;k++)
            for(int i=1;i<=nn;i++)
                Add_Edge(k,i,i+nn);
        while(m--)
        {
            scanf("%c%d%d%*c",&cmd,&u,&v);
            if(cmd == 'I')
            {
                for(int k=0;k<3;k++)
                {
                    Add_Edge(k,u,v+nn);
                    Add_Edge(k,v,u+nn);
                }
            }
            else
                Add_Edge(cmd-'X',u+nn,v);
        }
        printf("Case %d: ",++ncase);
        if(!Top_Sort(0) || !Top_Sort(1) || !Top_Sort(2))
            puts("IMPOSSIBLE\n");
        else
        {
            puts("POSSIBLE");
            for(int i=1;i<=nn;i++)
                printf("%d %d %d %d %d %d\n",V[0][i].dep,V[1][i].dep,V[2][i].dep,V[0][i+nn].dep,V[1][i+nn].dep,V[2][i+nn].dep);
            puts("");
        }
    }
    return 0;
}

参考:http://blog.csdn.net/dgq8211/article/details/8038993


  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  2. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  3. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept

  4. 代码是给出了,但是解析的也太不清晰了吧!如 13 abejkcfghid jkebfghicda
    第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3),为什么要这样拆分,原则是什么?

  5. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.