hdu-5695 Gym Class(贪心+拓扑排序)
发布日期:2021-08-19 16:00:59 浏览次数:1 分类:技术文章

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

题目链接:

Time Limit: 6000/1000 MS (Java/Others)   

 Memory Limit: 65536/65536 K (Java/Others)

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

 

Input
 
第一行一个整数
T,表示T(1T30) 组数据。
对于每组数据,第一行输入两个整数NM(1N100000,0M100000),分别表示总人数和某些同学的偏好。
接下来M行,每行两个整数A 和B(1A,BN),表示ID为A的同学不希望ID为B的同学排在他(她)之前。你可以认为题目保证至少有一种排列方法是符合所有要求的。
 

 

Output
 
对于每组数据,输出最大分数 。
 

 

Sample Input
 
3
1 0
2 1
1 2
3 1
3 1
 

 

Sample Output
 
1
2
6
 
 
题意:
 
 
思路:
 
涉及到先后问题就是拓扑序,而这个的拓扑序不止一种,而且要求最后的和最大,贪心知道要使ID值大的尽量排在前边,所以拓扑排序时用优先队列维护;
 
 
AC代码:
//#include 
#include
#include
#include
#include
#include
#include
#include
using namespace std;#define Riep(n) for(int i=1;i<=n;i++)#define Riop(n) for(int i=0;i
ve[N];priority_queue
qu;int main(){ int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); Riep(n)ve[i].clear(),vis[i]=0; int x,y; Riep(m) { scanf("%d%d",&x,&y); ve[x].push_back(y); ind[y]++; } for(int i=1;i<=n;i++) { if(!ind[i]) { qu.push(i); vis[i]=1; } } int cnt=0; while(!qu.empty()) { int fr=qu.top(); b[cnt++]=fr; qu.pop(); int len=ve[fr].size(); for(int i=0;i
b[i]) { mmin=b[i]; } sum=sum+mmin; } printf("%I64d\n",sum); } return 0;}

 

 

转载于:https://www.cnblogs.com/zhangchengc919/p/5515273.html

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

上一篇:hdu-5497 Inversion(滑动窗口+树状数组)
下一篇:poj1274 The Perfect Stall (二分最大匹配)

发表评论

最新留言

初次前来,多多关照!
[***.217.46.12]2024年03月01日 00时43分03秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

java学习手册下载_Java学习手册 2019-04-21
axios delete有请求体吗_关于axios请求——delete方法 2019-04-21
java 自助更改密码 api_搭建ldap自助修改密码系统--Self Service Password 2019-04-21
java 中断线程 wait_Java 线程中断(interrupt)与阻塞 (park)的区别 2019-04-21
java 豆瓣爬虫_谁说Java不能搞爬虫,阿婆主带你一起爬取豆瓣电影Top250 2019-04-21
java解非线性方程组_Scipy - 非线性方程组的所有解 2019-04-21
java isodate格式_fmt:formatDate的输出格式详解 2019-04-21
java16位字符串压缩成8位_在8位UART上发送16位值 2019-04-21
java selenium port_selenium java自动化测试 2019-04-21
java serializable深入了解_java serializable深入了解 2019-04-21
php 数组数值排序,按数值对PHP数组进行排序 2019-04-21
php 公私钥,PHP 实现 RSA 公私钥加密 2019-04-21
php 获取文件创建时间,php获取文件的创建时间、修改时间的简单示例 2019-04-21
php 判断 子集数组,php判断一个数组是另一个数组的子集_PHP教程 2019-04-21
matlab中notebook出错,MATLAB中notebook安装出现问题的解决 2019-04-21
matlab与情人节,情人节MATLAB画爱心的小礼物 2019-04-21
php如何强制下载文件,php 强制下载文件实现代码 2019-04-21
php继承exten,stylus中文文档 » 继承(@extend) » 张鑫旭-鑫空间-鑫生活 2019-04-21
mysql函数大全 pdf,MySQL函数大全 2019-04-21
php 常用文件系统函数,php 文件系统函数整理介绍 2019-04-21