本文共 1298 字，大约阅读时间需要 4 分钟。

Gym Class

Problem Description

今天，它终于当上了梦寐以求的体育课老师。第一次课上，它发现一个有趣的事情。在上课之前，所有同学要排成一列， 假设最开始每个人有一个唯一的ID，从1到N，在排好队之后，每个同学会找出包括自己在内的前方所有同学的最小ID，作为自己评价这堂课的分数。麻烦的是，有一些同学不希望某个（些）同学排在他（她）前面，在满足这个前提的情况下，新晋体育课老师——度度熊，希望最后的排队结果可以使得所有同学的评价分数和最大。

Input

对于每组数据，第一行输入两个整数N和M(1≤N≤100000,0≤M≤100000)，分别表示总人数和某些同学的偏好。

接下来M行，每行两个整数A 和B(1≤A,B≤N)，表示ID为A的同学不希望ID为B的同学排在他（她）之前。你可以认为题目保证至少有一种排列方法是符合所有要求的。

Output

Sample Input

Sample Output

priority_queue < int,vector < int > ,less < int > > q ; 优先队列从大到小排;

priority_queue < int,vector < int > , greater < int > > q; 优先队列从小到大排 ;

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;const int INF=0x3f3f3f3f;int topo[1000111];int head[1000111];int in[1000111];int N,num;struct node{    int to,next;}st[1000111];void add(int x,int y){    st[num].to=y;    st[num].next=head[x];    head[x]=num++;}void toposort(){    priority_queue 
       
        
         ,less
         
           > q; int i,j; int t=0; int sum=INF; long long ans=0; for(i=N;i>=1;i--) if(in[i]==0) q.push(i); while(!q.empty()) { int w=q.top(); q.pop(); topo[t++]=w; in[w]=-1; for(i=head[w];i!=-1;i=st[i].next) { in[st[i].to]--; if(in[st[i].to]==0) q.push(st[i].to); } } for(i=0;i
         
        
       
      
     
    
   

转载地址：https://blog.csdn.net/WYK1823376647/article/details/52224741 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！