Gym Class

Time Limit: 6000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 1090    Accepted Submission(s): 437 Problem Description 众所周知，度度熊喜欢各类体育活动。 今天，它终于当上了梦寐以求的体育课老师。第一次课上，它发现一个有趣的事情。在上课之前，所有同学要排成一列， 假设最开始每个人有一个唯一的ID，从1到 N ，在排好队之后，每个同学会找出包括自己在内的前方所有同学的最小ID，作为自己评价这堂课的分数。麻烦的是，有一些同学不希望某个（些）同学排在他（她）前面，在满足这个前提的情况下，新晋体育课老师——度度熊，希望最后的排队结果可以使得所有同学的评价分数和最大。   Input 第一行一个整数 T ，表示 T(1≤T≤30) 组数据。 对于每组数据，第一行输入两个整数 N 和 M(1≤N≤100000,0≤M≤100000) ，分别表示总人数和某些同学的偏好。 接下来 M 行，每行两个整数 A 和 B(1≤A,B≤N) ，表示ID为 A 的同学不希望ID为 B 的同学排在他（她）之前。你可以认为题目保证至少有一种排列方法是符合所有要求的。   Output 对于每组数据，输出最大分数 。   Sample Input 3 1 0 2 1 1 2 3 1 3 1   Sample Output 1 2 6   Source 2016"百度之星" - 初赛（Astar Round2A）   Recommend wange2014   |   We have carefully selected several similar problems for you:   5842  5841  5840  5839  5838   

拓扑排序+优先队列+邻接表。

#include<cstdio> #include<iostream> #include<cstring> #include<cmath> #include<queue> #include<algorithm> using namespace std; const int N = 100005; struct node { int v,next; } s[N]; int head[N],degree[N],a[N]; int cnt,n,m,temp; void add(int a,int b) { s[cnt].v=b; s[cnt].next=head[a]; head[a]=cnt++; degree[b]++; } void topo() { priority_queue<int,vector<int>,less<int> >Q; for(int l=1; l<=n; l++) { if(!degree[l]) Q.push(l); } temp=0; while(!Q.empty()) { int top=Q.top(); Q.pop(); a[temp++]=top; for(int i=head[top]; i!=-1; i=s[i].next) { int v=s[i].v; degree[v]--; if(!degree[v]) { Q.push(v); } } } } int main() { int T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); cnt=0; memset(head,-1,sizeof(head)); memset(degree,0,sizeof(degree)); for(int i=0; i<m; i++) { int a,b; scanf("%d%d",&a,&b); add(a,b); } topo(); int flag=1000000; __int64 ans=0; //没想到答案超int 哇了一次。 for(int i=0; i<temp; i++) { flag=min(flag,a[i]); ans=ans+flag; } printf("%I64d\n",ans); } return 0; } 题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=5695