HDU 5695 Gym Class && 百度之星 初赛 1006

时间：2023-08-26 17:21:30

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5695

本文链接:http://www.cnblogs.com/Ash-ly/p/5515234.html

题意:

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

　　第一行输入T,表示有T组数据.对于每组数据的第一行有两个数字N和M,代表总人数和某些同学的偏好,接下来M行,有两个数字Ａ和Ｂ表示Ａ不想让Ｂ站在他的前面．对于每组输入输出最大分数．

思路：

　　如果Ａ不想让Ｂ在他的前面,那么就可以认为Ａ到Ｂ有一条有向边,那么就可以利用拓扑序列来做这道题了,但是要想每次首先访问到的是能访问到的中的最大值,那么可以把入度为零的所有点压入优先队列中,使得每次新的拓展节点是能拓展的种的最大值.

代码:

 #include <iostream>

 #include <cmath>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <algorithm>

 #include <queue>

 #include <stack>

 #include <vector>

 using namespace std;

 typedef long long LL;

 const int MAXN = ;

 vector<int> map[MAXN + ];//图

 int inder[MAXN + ];//入度

 int main(){

     //freopen("input.txt", "r", stdin);

     int T;

     scanf("%d", &T);

     while(T--){

         int n, m;

         scanf("%d%d", &n, &m);

         for(int i = ; i <= n; i++)map[i].clear();

         memset(inder, , sizeof(inder));

         for(int i = ; i <= m; i++){

             int u, v;

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

             map[u].push_back(v); // u 到 v 有一条有向边

             inder[v]++;

         }

         priority_queue<int> Qu;

         for(int i = ; i <= n; i++) if(!inder[i]) Qu.push(i);//刚开始所有入度为0的点进队

         LL ans = ;

         int minu = n + ;

         while(!Qu.empty()){

             int head = Qu.top(); //获得下一个待扩展节点,一定是当前可扩展节点中最大的

             Qu.pop();

             minu = min(minu, head);//每个人的分数等于他以及他之前的人的编号的最小值

             ans +=(LL) minu;

             for(int i = ; i < map[head].size(); i++)

                 if( !(--inder[map[head][i]]) )//每访问一个点,就把从这个点出发的有向边删除,删除后出现新的入度为0的点,则进队

                     Qu.push(map[head][i]);

         }

         printf("%lld\n", ans);

     }

     return ;

 }

相关文章