集训队分组

Dear 丶 2022-06-14 07:52 218阅读 0赞

中南大学ACM的暑期集训马上就要开始了，这次集训会将全体N名集训队员（编号分别为1, 2, …, N）按集训选拔赛的排名分成两组，前K名队员分入A组，其余队员分入B组。

但现在助理教练CSGrandeur一不小心把集训选拔赛的排名弄丢了，而之前又没将A组和B组的人员确定出来，于是CSGrandeur打算问一下集训人员他们的名次各是怎样的，以此来确定一下A组的队员。

然而集训队员们都视名次如粪土，只是隐约记得某些人排在了自己的后面，最终反馈到CSGrandeur这里的一共有M条信息，每条信息都可以用一个二元组(x, y) (x!=y)表示，含义为第x名队员记得第y名队员的排名比自己的要靠后。

现在CSGrandeur想知道，根据这M条信息，是否可以确定出A组的队员呢？（默认所有集训队员反映的信息都是符合事实的。）

## Input ##

输入包含多组测试数据。

对于每组测试数据，第一行包含三个正整数N (2<=N<=1000)、K (1<=K<=N)、M (1<=M<=10000)，含义同上。接下来M行每行有两个正整数x、y (1<=x, y<=N且x!=y)，分别描述了M条信息，对于每对x、y，均表示第x名队员记得第y名队员的排名比自己的要靠后。

## Output ##

对于每组测试数据，如果可以确定出A组的队员，输出“YES”（不包括引号），否则输出“NO”（不包括引号）。

## Sample Input ##

3 1 21 21 33 2 21 21 3

## Sample Output ##

YESNO

思路：能确定为属于A组的k个成员  就是说至少有n-k个人排名在这个人后面，所以只要判断每个人后面是否存在至少n-k个人即可，

bfs加邻接表

#include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <queue>
    #include <vector>
    #include <cstring>
    using namespace std;
    int vis[1010];
    vector<int> v[1010];
    int bfs(int index)
    {
        queue<int> Q;
        memset(vis,0,sizeof(vis));
        int ans=0;
        Q.push(index);
        vis[index]=1;
        while(!Q.empty())
        {
            int xx=Q.front();
            Q.pop();
            for(int i=0;i<v[xx].size();i++)
            {
                 int y=v[xx][i];
                 if(!vis[y])
                 {
                      ans++;
                      Q.push(y);
                      vis[y]=1;
                 }
            }
        }
        return ans;
    }
    int main()
    {
        int n,k,m;
        while(~scanf("%d %d %d",&n,&k,&m))
        {                     
            int x,y;
            for(int i=0;i<1010;i++)
            {
                v[i].clear();
            }
            memset(vis,0,sizeof(vis));
            for(int i=0;i<m;i++)
            {
                scanf("%d %d",&x,&y);
                v[x].push_back(y);
            }
            int sum=0;
            for(int i=1;i<=n;i++)
            {
                if(bfs(i)>=(n-k))
                {
                    sum++;
                }
            }
            if(sum>=k)
            printf("YES\n");
            else
            printf("NO\n");
        } 
        return 0;
    }