1 条题解

  • 0
    @ 2021-6-15 14:44:01

    C++ :

    #include<cstdio>
    using namespace std;
    
    bool f=true;
    int n,num,top,matrix[30][30],ru[30],chu[30],zhan[30],ans[30];
    struct Photo{//幻灯片 
        int Xmin,Xmax,Ymin,Ymax;
    }; 
    Photo photo[30];
    
    struct Node{
        int x,y;
    };
    Node node[30];
    
    void PRINT()
    {
        for (int i=1; i<=n-1; i++)
            printf("%c %d\n",i+'A'-1,ans[i]);//强制类型转换的技巧 
        printf("%c %d",n+'A'-1,ans[n]);
    }
    
    int main()
    {
        scanf("%d",&n);
        for (int i=1; i<=n; i++)
            scanf("%d%d%d%d",&photo[i].Xmin,&photo[i].Xmax,&photo[i].Ymin,&photo[i].Ymax);
        for (int i=1; i<=n; i++)
            scanf("%d%d",&node[i].x,&node[i].y);
        for (int i=1; i<=n; i++)
            for (int j=1; j<=n; j++)
                if (node[j].x>=photo[i].Xmin&&node[j].x<=photo[i].Xmax&&node[j].y>=photo[i].Ymin&&node[j].y<=photo[i].Ymax)
                {
                    matrix[i][j]=1;//不能用bush表存,不好操作.第i张幻灯片指向第j个点 
                    chu[i]++;
                }
        for (int i=1; i<=n; i++) ru[i]=chu[i]-1;//入度为出度-1 
        while (num!=n)
        {
            int ss=0;//记录本次入度为0的点的个数,用来判断是否有环 
            for (int i=1; i<=n; i++)
            {
                if (ru[i]==0)
                {
                    num++; ss++; zhan[++top]=i;
                    for (int j=1; j<=n; j++)
                        if (matrix[i][j])
                            { ans[i]=j; break; }//break 一点小优化:入度为0的点出度为1
                    ru[i]=0x7fffffff; //相当于开一个bool数组,每个点只入栈一次 
                }
            }
            if (ss==0) { f=false; break; }
            for (int i=1; i<=ss; i++)//去掉相连的边 
            {
                int now=zhan[top];
                top--;
                for (int j=1; j<=n; j++)
                    if (matrix[j][ans[now]])
                    {
                        matrix[j][ans[now]]=0;
                        ru[j]--;
                    }
            }
        }
        if (f) PRINT();
        else printf("None");
        return 0;
    }
    
    
    • 1

    信息

    ID
    1042
    时间
    1000ms
    内存
    256MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者