hdu3231 (三重拓扑排序) 2009 Asia Wuhan Regional Contest Hosted by Wuhan University

这道题算是我拓扑排序入门的收棺题了，卡了我好几天，期间分别犯了超时，内存溢出，理解WA，细节WA，格式WA……

题目的意思大概是在一个三维坐标系中，有一大堆矩形，这些矩形的每条棱都与坐标轴平行。

这些矩形有4种情况——

1. 有重合部分（I a b）表示a与b重合；

2. a的x坐标大于b的x坐标（X a b），表示a的最大的x坐标大于b的最小的x坐标；

3. （Y a b）y坐标，同上；

4. （Z a b）z坐标，同上；

也就是说，我们可以把每个矩形ai按照三个方向分解，分别为——平行于xoy平面的ai的上平面a01和ai的下平面a02，平行于xoz平面的ai的左平面a11和ai的右平面a12，平行于yoz平面的ai的前平面a21和ai的后平面a22。

假设有（I a b），那么表示a01 < b02, a02 < b01; a11 < b12, a12 < b11; a21 < b22, a22 < b21;

假设有（X a b），那么表示a02 < b01;

假设有（Y a b），那么表示a12 < b11;

假设有（Y a b），那么表示a22 < b21;

同时，每个矩形自身有特点：a01 < a02, a11<a12, a21 < a22;

然后我们就分别获得了关于所有矩形的三个平面上的拓扑关系，然后分别对三个平面进行拓扑排序，如果有一组不满足，那么就输出不可能。

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <queue>
  4 using namespace std;
  5 
  6 const int N = 1010;
  7 const int M = 100010;
  8 
  9 struct Node
 10 {
 11     int val[3];
 12     int ds[3];
 13 }s[N<<2];   //保存每个平面的坐标值和深度（前面有几个平面）
 14 
 15 struct node
 16 {
 17     int to;
 18     int next;
 19 }eage[3][M<<1];     //每组平面之间的关系
 20 
 21 int n, m;
 22 int a, b;
 23 char ch[2];
 24 int head[3][M<<1];      
 25 int tm = 1;
 26 int k[3];
 27 
 28 bool tsort(int x)
 29 {
 30     queue<int> que;
 31 
 32     int sum = 0;
 33     for(int i = 2; i <= 2*n+1; i++)
 34     {
 35         if(s[i].ds[x] == 0)
 36         {
 37             que.push(i);
 38             s[i].val[x] = 0;
 39         }
 40     }
 41     while(!que.empty())
 42     {
 43         int p = que.front();
 44         que.pop();
 45         s[p].ds[x]--;
 46         sum++;
 47 
 48         for(int i = head[x][p]; i != -1; i = eage[x][i].next)
 49         {
 50             int v = eage[x][i].to;
 51             s[v].ds[x]--;
 52             if(s[v].ds[x] == 0)
 53             {
 54                 que.push(v);
 55                 s[v].val[x] = s[p].val[x]+1;
 56             }
 57         }
 58     }
 59     if(sum == 2*n) return 1;
 60     return 0;
 61 }
 62 
 63 void get(int x, int a, int b)
 64 {
 65     eage[x][k[x]].to = b;
 66     eage[x][k[x]].next = head[x][a];
 67     head[x][a] = k[x]++;
 68     s[b].ds[x]++;
 69 }
 70 
 71 int main()
 72 {
 73     //freopen("test.txt", "r", stdin);
 74     while(~scanf("%d%d", &n, &m) && (n+m))
 75     {
 76         memset(k, 0, sizeof(k));
 77         memset(head, -1, sizeof(head));
 78         memset(s, 0, sizeof(s));
 79 
 80         while(m--)
 81         {
 82             scanf("%s%d%d", ch, &a, &b);
 83             if(ch[0] == 'I')
 84             {
 85                 for(int i = 0; i < 3; i++)
 86                 {
 87                     get(i, 2*a, 2*b+1);
 88                     get(i, 2*b, 2*a+1);
 89                 }
 90             }
 91             else get(ch[0]-'X', 2*a+1, 2*b);
 92         }
 93         for(int i = 1; i <= n; i++)
 94             for(int j = 0; j < 3; j++) get(j, 2*i, 2*i+1);
 95 
 96         printf("Case %d: ", tm++);
 97         bool p = 0;
 98         for(int i = 0; i < 3; i++)
 99         {
100             if(!tsort(i))
101             {
102                 printf("IMPOSSIBLE

");
103                 p = 1;
104                 break;
105             }
106 
107         }
108         if(p) continue;
109 
110         printf("POSSIBLE
");
111         for(int i = 2; i <= 2*n+1; i++)
112         {
113             for(int j = 0; j < 3; j++)
114             {
115                 printf("%d", s[i].val[j]);
116                 if(i%2 == 0|| j < 2) printf(" ");
117                 else printf("
");
118             }
119         }
120         printf("
");
121     }
122     return 0;
123 }

代码姿势和大神比还是很挫……需要继续努力！