Gym Class
题意：在上课之前，所有同学要排成一列， 假设最开始每个人有一个唯一的ID，从1到，在排好队之后，每个同学会找出包括自己在内的前方所有同学的最小ID，作为自己评价这堂课的分数。麻烦的是，有一些同学不希望某个（些）同学排在他（她）前面，在满足这个前提的情况下，新晋体育课老师——度度熊，希望最后的排队结果可以使得所有同学的评价分数和最大。
Input 第一行一个整数T，表示 T组数据。 对于每组数据，第一行输入两个整数N和M，分别表示总人数和某些同学的偏好。 接下来M行，每行两个整数A 和B，表示ID为A的同学不希望ID为B的同学排在他（她）之前。你可以认为题目保证至少有一种排列方法是符合所有要求的。 Output 对于每组数据，输出最大分数 。 Sample Input 3 1 0 2 1 1 2 3 1 3 1 Sample Output 1 2 6
题解：有一部分的排序是特定顺序，所以用拓扑排序+优先队列，无特殊要求的数字入度为0，可以按从大到小排序，遇到入度不为0的再加入队列。
#include<cstdio> #include<queue> #include<cstring> #define M 111111 #define MA 0x3f3f3f3f using namespace std; int t,n,m; int edgenum; struct node{ int u,v,next; }sc,edge[M]; int head[M],inter[M],ans[M]; void init(){ edgenum=0; memset (head,-1,sizeof(head)); memset (inter,0,sizeof(inter)); } void addedge(int uu,int vv){ edge[edgenum].v=vv; edge[edgenum].next=head[uu]; head[uu]=edgenum++; inter[vv]++;; } void topo(){ priority_queue<int>q; int i,j; while (!q.empty()) q.pop(); for (i=1;i<=n;i++){ if (inter[i]==0) q.push(i); } for (int pos=1;pos<=n;pos++){ int f=q.top(); ans[pos]=f; q.pop(); for (int k=head[f];k!=-1;k=edge[k].next){ int la=edge[k].v; inter[la]--; if (inter[la]==0) q.push(la); } } } int main(){ scanf ("%d",&t); int i; while (t--){ init(); scanf ("%d %d",&n,&m); while (m--){ scanf ("%d %d",&sc.u,&sc.v); addedge(sc.u,sc.v); } topo(); long long sum=0,mini=MA;//注意long long for (i=1;i<=n;i++){ mini=min(mini,(long long)ans[i]);//每次都加最小的 sum+=mini; } printf ("%lld\n",sum); } return 0; }
