#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
struct Edge{
    int xmin,xmax,ymin,ymax;
}edge[30];
int mat[30][30]; //section i ,point j 
int x[30],y[30],n,i,j,f,t,l;
int cnt[30],cnt2[30];
int print_[30];
int main()
{
    /*freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);*/
    queue<int> q;
    cin>>n;
    l=n;
    for(i=1;i<=n;i++)
    cin>>edge[i].xmin>>edge[i].xmax>>edge[i].ymin>>edge[i].ymax;
    for(i=1;i<=n;i++) 
    {
    cin>>x[i]>>y[i];
       for(j=1;j<=n;j++)
       {
        if(x[i]>edge[j].xmin&&x[i]<edge[j].xmax&&y[i]>edge[j].ymin&&y[i]<edge[j].ymax)
        {
            mat[j][i]=1;cnt[i]++;
        }
       }
    }
    for(i=1;i<=n;i++)
    if(cnt[i]==1) q.push(i);
    
    if(q.empty()!=0) {
        cout<<"None";return 0;
    }
    while(!q.empty())
    {   f=0; 
        t=q.front();
        for(i=1;i<=n;i++)
        if(mat[i][t]) 
        break;
        
        print_[i]=t;//cout<<i<<" "<<print_[i]<<endl;
        cnt[t]=0;mat[i][t]=0;
        for(j=1;j<=n;j++)
        {   
          if(mat[i][j]) 
          {        
          mat[i][j]=0;
           cnt[j]--;

          }
          if(cnt[j]==1) 
          {
           q.push(j);
           f=1;
          }
        }
        if(f!=1&&q.size()!=1) {
            cout<<"None";return 0;
        }
        q.pop();
    }
    for(i=1;i<=n;i++)
    cout<<char(i+64)<<" "<<print_[i]<<endl;
    return 0;
}

过了样例,但是错了两个点

1 条评论

  • @ 2019-08-03 13:34:05

    过啦!

    #include<iostream>
    #include<cstdio>
    #include<queue>
    using namespace std;
    struct Edge{
        int xmin,xmax,ymin,ymax;
    }edge[30];
    int mat[30][30]; //section i ,point j 
    int x[30],y[30],n,i,j,f,t,l;
    int cnt[30],cnt2[30];
    int print_[30];
    int main()
    {
        /*freopen("slides3.in","r",stdin);
        freopen("out.txt","w",stdout);*/
        queue<int> q;
        cin>>n;
        l=n;
        for(i=1;i<=n;i++)
        cin>>edge[i].xmin>>edge[i].xmax>>edge[i].ymin>>edge[i].ymax;
        for(i=1;i<=n;i++) 
        {
        cin>>x[i]>>y[i];
           for(j=1;j<=n;j++)
           {
            if(x[i]>=edge[j].xmin&&x[i]<=edge[j].xmax&&y[i]>=edge[j].ymin&&y[i]<=edge[j].ymax)
            {
                mat[j][i]=1;cnt[i]++;
            }
           }
        }
        for(i=1;i<=n;i++)
        {
         if(cnt[i]==0)
              {
                cout<<"None";return 0;
              } 
         if(cnt[i]==1) 
         {
         q.push(i);cnt[i]=-1;
         }
        }
        if(q.empty()!=0) {
            cout<<"None";return 0;
        }
        while(!q.empty())
        {   
            f=0;
            t=q.front();
            for(i=1;i<=n;i++)
            if(mat[i][t]) 
            break;
            
            print_[i]=t;//
            
            mat[i][t]=0;
            for(j=1;j<=n;j++)
            {
              if(mat[i][j]) 
              {        
              mat[i][j]=0;
              cnt[j]--; 
              if(cnt[j]==1)                     
               q.push(j);//曾在此处出现冗余入队 //cout<<"!";break;
              }
            }
            
            q.pop();l--;
        }
        if(l!=0) {
            cout<<"None";return 0;
        }
        for(i=1;i<=n;i++)
        cout<<char(i+64)<<" "<<print_[i]<<endl;
        return 0;
    }
    
  • 1

信息

难度
8
分类
(无)
标签
递交数
15
已通过
5
通过率
33%
被复制
2
上传者