首页 > 代码库 > HDU 3213 Box Relations（拓扑排序构造）

HDU 3213 Box Relations（拓扑排序构造）

2024-07-09 00:15:40   220人阅读

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3231

题意：有n个长方体，四种限制条件。（1）I x y x和y有相交；（2）X/Y/Z  x y x的最大X/Y/Z坐标小于y的最大X/Y/Z。构造出这样的n个长方体。

 思路：首先，XYZ三个方向是可以分开考 虑的。那么我们可以一个个分别求解。将每个长方体拆成左上角右下角两个点，我们假设现在考虑X方向，也即是一个长方体对应两个X方向的点，共2*n个点， 边<i,j>表示i小于j，那么首先有边<i,i+n>，即同一个长方体的左下角的点的x坐标必然小于其右上角的x坐标。对于相 交的x和y有<x,y+n> <y,x+n>，对于不相交的有<x+n,y>。然后就是判断是不是拓扑图就行了。是的话依次按照0,1,2开始标号。

 

vector<int> g[3][N];int d[3][N],ans[3][N],n,m;void Add(int i,int u,int v){    g[i][u].pb(v);    d[i][v]++;}void build(){    int i,j,x,y;    FOR0(i,3) FOR0(j,N) g[i][j].clear(),d[i][j]=0;    char op[5];    FOR0(i,3) FOR1(j,n) Add(i,j,j+n);    while(m--)    {        RD(op); RD(x,y);        if(op[0]==‘I‘)        {            FOR0(i,3) Add(i,x,y+n),Add(i,y,x+n);        }        else Add(op[0]-‘X‘,x+n,y);    }}int top_sort(int t){    int cnt=0;    queue<int> Q;    int i,j,u;    FOR1(i,n+n) if(!d[t][i]) ans[t][i]=cnt++,Q.push(i);    while(!Q.empty())    {        j=Q.front();        Q.pop();        FOR0(i,SZ(g[t][j]))        {            u=g[t][j][i];            if(--d[t][u]==0) Q.push(u),ans[t][u]=cnt++;        }    }    return cnt==n+n;}void deal(){    int i;    FOR0(i,3) if(!top_sort(i))    {        puts("IMPOSSIBLE");        return;    }    puts("POSSIBLE");    FOR1(i,n) printf("%d %d %d %d %d %d\n",ans[0][i],ans[1][i],ans[2][i],ans[0][i+n],ans[1][i+n],ans[2][i+n]);}int main(){    int num=0;    Rush(n)    {        RD(m);        if(!n&&!m) break;        build();        printf("Case %d: ",++num);        deal(); puts("");    }}

 

 

 


联系
我们