这道题算是我拓扑排序入门的收棺题了，卡了我好几天，期间分别犯了超时，内存溢出，理解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;
然后我们就分别获得了关于所有矩形的三个平面上的拓扑关系，然后分别对三个平面进行拓扑排序，如果有一组不满足，那么就输出不可能。
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std; const int N = ;
const int M = ; struct Node
{
int val[];
int ds[];
}s[N<<]; //保存每个平面的坐标值和深度（前面有几个平面） struct node
{
int to;
int next;
}eage[][M<<]; //每组平面之间的关系 int n, m;
int a, b;
char ch[];
int head[][M<<];
int tm = ;
int k[]; bool tsort(int x)
{
queue<int> que; int sum = ;
for(int i = ; i <= *n+; i++)
{
if(s[i].ds[x] == )
{
que.push(i);
s[i].val[x] = ;
}
}
while(!que.empty())
{
int p = que.front();
que.pop();
s[p].ds[x]--;
sum++; for(int i = head[x][p]; i != -; i = eage[x][i].next)
{
int v = eage[x][i].to;
s[v].ds[x]--;
if(s[v].ds[x] == )
{
que.push(v);
s[v].val[x] = s[p].val[x]+;
}
}
}
if(sum == *n) return ;
return ;
} void get(int x, int a, int b)
{
eage[x][k[x]].to = b;
eage[x][k[x]].next = head[x][a];
head[x][a] = k[x]++;
s[b].ds[x]++;
} int main()
{
//freopen("test.txt", "r", stdin);
while(~scanf("%d%d", &n, &m) && (n+m))
{
memset(k, , sizeof(k));
memset(head, -, sizeof(head));
memset(s, , sizeof(s)); while(m--)
{
scanf("%s%d%d", ch, &a, &b);
if(ch[] == 'I')
{
for(int i = ; i < ; i++)
{
get(i, *a, *b+);
get(i, *b, *a+);
}
}
else get(ch[]-'X', *a+, *b);
}
for(int i = ; i <= n; i++)
for(int j = ; j < ; j++) get(j, *i, *i+); printf("Case %d: ", tm++);
bool p = ;
for(int i = ; i < ; i++)
{
if(!tsort(i))
{
printf("IMPOSSIBLE\n\n");
p = ;
break;
} }
if(p) continue; printf("POSSIBLE\n");
for(int i = ; i <= *n+; i++)
{
for(int j = ; j < ; j++)
{
printf("%d", s[i].val[j]);
if(i% == || j < ) printf(" ");
else printf("\n");
}
}
printf("\n");
}
return ;
}
代码姿势和大神比还是很挫……需要继续努力！