题目链接HDU-3231 题是好题，就是输出格式略坑。。少空行他不会提示PE只显示WA 对于给定的n个盒子，我们可以将其起始点和终点分别假定为i和i+n, 这样我们就可以在每个维度（x,y,z）上得到2n个点
在初始化的时候，考虑初始约束条件 x<x+n,y<y+n,z<z+n 在初始时已经就应该要连边，需要单独初始化
然后考虑“I”，“X”，“Y”，“Z”的询问更新， 当为“I”时，a,b没有相交关系，在三个维度上添加约束条件a<b+n,b<a+n(这个约束条件非常巧妙) 当为“X”，“Y”，“Z”时，给a，b在相应维度上连边 “a+n<b”; 按照对应约束条件完成建图
再对三个维度分别跑一次拓扑排序即可
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <map> #include <queue> #include <functional> #include <vector> #include <stack> #include <set> #include <bitset> using namespace std; typedef long long ll; const int maxn=2e5+50; const int inf=0x7fffffff; const int mod=1e9+7; const int HASH=131; vector<int> v[3][maxn];//代表维度分别为xyz int degree[3][maxn]; int dis[3][maxn]; void init(int n) { for(int i=0;i<3;i++) { for(int j=1;j<=2*n;j++) { degree[i][j]=dis[i][j]=0; v[i][j].clear(); } } for(int i=0;i<3;i++) { for(int j=n+1;j<=2*n;j++) { degree[i][j]++; v[i][j-n].push_back(j); } } } int main() { int n,m; int cass=1; while(scanf("%d%d",&n,&m)!=EOF&&n+m)//初始将最大的盒子长度定为n { init(n); for(int ttt=1;ttt<=m;ttt++) { char s[5]; int a,b; scanf("%s %d %d",s,&a,&b); if(s[0]=='I') { for(int i=0;i<3;i++) { v[i][a].push_back(b+n); degree[i][b+n]++; v[i][b].push_back(a+n); degree[i][a+n]++; } } else if(s[0]=='X') { v[0][a+n].push_back(b); degree[0][b]++; } else if(s[0]=='Y') { v[1][a+n].push_back(b); degree[1][b]++; } else if(s[0]=='Z') { v[2][a+n].push_back(b); degree[2][b]++; } } printf("Case %d: ",cass++); int sign=0; for(int i=0;i<3;i++) { queue<int> q; int cnt=0;//统计进入队列数量，并给距离赋初始值 for(int j=1;j<=n;j++) { if(degree[i][j]==0) { q.push(j); dis[i][j]=cnt++; } } while(!q.empty())//找每个维度上入度为0的点 { int tmp=q.front(); q.pop(); int len=v[i][tmp].size(); for(int j=0;j<len;j++) { int t=v[i][tmp][j]; dis[i][t]=max(dis[i][t],dis[i][tmp]+1);//让距离满足约束条件 if(--degree[i][t]==0) { q.push(t); cnt++; } } } if(cnt!=2*n) sign=1; } if(sign) { printf("IMPOSSIBLE\n"); } else { printf("POSSIBLE\n"); for(int i=1;i<=n;i++) { printf("%d %d %d %d %d %d\n",dis[0][i],dis[1][i],dis[2][i],dis[0][i+n],dis[1][i+n],dis[2][i+n]); } } cout<<endl; } return 0; }