CSU 1081 集训队分组

时间：2022-06-07 06:22:05

题意：有n个学生，比了一场比赛，但是榜单看不到了。现在告诉你m段信息，每段信息的内容是(a,b)，表示a的排名比b的高。问你能不能根据这些信息得出这场比赛的前k名。

思路：用拓扑排序找出一组符合k个人的解，然后判断这组解是否唯一，如果这组解是唯一的，那么剩下的n-k个人一定都在这k个人后面。dfs一下就行了。

代码：

 #include<stdio.h>

 #include<string.h>

 const int N=,M=;

 struct node

 {

     int v,next;

 }e[M];

 int head[N],cnt,d[N],mark[N],p[N],js,tmp[N];

 void add(int u,int v)

 {

     e[cnt].v=v,e[cnt].next=head[u];

     head[u]=cnt++;

 }

 void dfs(int u)

 {

     if(!p[u]&&!mark[u])    js++;

     p[u]=;

     for(int i=head[u];i!=-;i=e[i].next)

     {

         if(!p[e[i].v])

             dfs(e[i].v);

     }

 }

 int main()

 {

     int n,m,k,i,u,v,f,j;

     while(scanf("%d%d%d",&n,&k,&m)!=EOF)

     {

         memset(head,-,sizeof(head));

         memset(d,,sizeof(d));

         memset(mark,,sizeof(mark));

         js=cnt=;

         while(m--)

         {

             scanf("%d%d",&u,&v);

             add(u,v);

             d[v]++;

         }

         while(js<k)

         {

             for(i=;i<=n&&d[i];i++);

             tmp[++js]=i;mark[i]=;

             d[i]--;

             for(i=head[i];i!=-;i=e[i].next)

                 d[e[i].v]--;

         }

         for(i=;i<=k;i++)

         {

             memset(p,,sizeof(p));

             js=;

             dfs(tmp[i]);

             if(js!=n-k)    break;

         }

         if(i>k)    printf("YES\n");

         else        printf("NO\n");

     }

     return ;

 }

参考文章：http://www.cnblogs.com/algorithms/archive/2012/07/02/2573631.html

相关文章