首页 > 代码库 > HDU3231 Box Relations——三维拓扑刨铣
HDU3231 Box Relations——三维拓扑刨铣
HDU3231 Box Relations
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3231
题目意思:在一个三维空间上有一些棱和坐标轴平行的立方体。给够给予四种关系。I i j表示i,j两个立方体是有部分的重合,X i j表示立方体i所有点x坐标都小于立方体j的x坐标,Y i j表示立方体i所有点y坐标都小于立方体j的y坐标,Z i j表示立方体i所有点Z坐标都小于立方体j的Z坐标。然后给出一系列这样的关系,问你这些关系是否存在矛盾,如果不矛盾,对于每个立方体输出六个参数x1,y1,z1,x2,y2,z2,分别代表x坐标的下界,y坐标的下界,z坐标的下界,x坐标的上界,y坐标的上界,z坐标的上界。
思路:在每个维度上分别拓扑排序。具体思路还没有想的特别懂,大概明年了。还没想好怎么总结。这个坑以后再来补好了。
代码 :
//Author: xiaowuga #include <bits/stdc++.h> #define maxx INT_MAX #define minn INT_MIN #define inf 0x3f3f3f3f const long long N=2000+10; using namespace std; typedef long long LL; vector<int>mapt[3][N];//3代表三个维度 int in[3][N],v[3][N],n; void init(){ for(int i=0;i<3;i++) for(int j=1;j<=n*2;j++){ in[i][j]=v[i][j]=0; mapt[i][j].clear(); } for(int i=0;i<3;i++)//坐标x,y,z for(int j=1;j<=n;j++){//盒子j,用两个点来表示,点j和j+n in[i][j+n]++; mapt[i][j].push_back(j+n);//点j的坐标比相应的点j+n的坐标小 } } int topo(){ for(int i;i<3;i++){ int k=0; queue<int>q; for(int j=1;j<=n;j++){ if(in[i][j]==0){ q.push(j); k++;//对于入度为0的起点,作为拓扑起点 } } //拓扑套路 while(!q.empty()){ int s=q.front();q.pop(); for(int j=0;j<mapt[i][s].size();j++){ int t=mapt[i][s][j]; if(v[i][s]+1>v[i][t]) v[i][t]=v[i][s]+1;//t是s的后续所以s一定比t大是不合理的,所以我们需要更新t节点的坐标至少为s的坐标+1 if(--in[i][t]==0){ q.push(t);k++; } } } if(k!=n*2) return 0;//如果在其中一个维度不满足关系则说明不满足 } return 1; } int main() { ios::sync_with_stdio(false);cin.tie(0); char ch; int m,a,b,c=0; while(cin>>n>>m&&(n+m)){ init(); //我们添加的边实际上是一种关系,我们把a当成第a个盒子的起点,a+n当成第a个盒子的终点 while(m--){ cin>>ch>>a>>b; //如果他们是相交的 if(ch==‘I‘){ for(int i=0;i<3;i++){ mapt[i][a].push_back(b+n);in[i][b+n]++;//a的起点小于b的终点 mapt[i][b].push_back(a+n);in[i][a+n]++;//b的起点小于a的终点 //说明a b是相交的 } } else if(ch==‘X‘) {mapt[0][a+n].push_back(b);in[0][b]++;}//在x轴上a的终点小于b的起点 else if(ch==‘Y‘) {mapt[1][a+n].push_back(b);in[1][b]++;}//在y轴上a的终点小于b的起点 else if(ch==‘Z‘) {mapt[2][a+n].push_back(b);in[2][b]++;}//在z轴上a的终点小于b的起点 } cout<<"Case "<<++c<<": "; if(!topo()) cout<<"IMPOSSIBLE"<<endl; else{ cout<<"POSSIBLE"<<endl; for(int i=1;i<=n;i++){ cout<<v[0][i]; for(int j=1;j<3;j++) cout<<" "<<v[j][i]; for(int j=0;j<3;j++) cout<<" "<<v[j][i+n]; cout<<endl; } } cout<<endl; } return 0; }
HDU3231 Box Relations——三维拓扑刨铣
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。