HDU-5695-拓扑排序+优先队列
2024-08-22 12:26:08
Gym Class
Time Limit: 6000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2193 Accepted Submission(s): 835
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
1 0
2 1
1 2
3 1
3 1
Sample Output
1
2
6
2
6
Source
对这个图进行拓扑排序,但注意要优先选择权值较大的点加入,才能使得结果最大化。用优先队列。
#include<bits/stdc++.h>
using namespace std;
#define LL long long
int tot[];
vector<int>e[];
int main(){
int t,n,m,i,j,k;
int a,b;
cin>>t;
while(t--){
priority_queue<int,vector<int>,less<int> >q;
cin>>n>>m;
memset(tot,,sizeof(tot));
for(i=;i<=m;++i){
scanf("%d%d",&a,&b);
e[a].push_back(b);
tot[b]++;
}
for(i=;i<=n;++i){
if(tot[i]==) q.push(i);
}
LL ans=;
LL minn=;
while(!q.empty()){
int u=q.top();
q.pop();
if(u<minn) minn=u;
ans+=minn;
for(i=;i<e[u].size();++i){
if(!(--tot[e[u][i]])) q.push(e[u][i]);
}
}
cout<<ans<<endl;
for(i=;i<=n;++i) e[i].clear();
}
return ;
}
最新文章
- 关于CAJViewer 无法获取document路径问题
- boost 相关
- ActiveRecord 模式杂谈
- 丢手帕问题as3版
- coursera无法观看视频解决方法
- C# (类型、对象、线程栈和托管堆)在运行时的相互关系
- C++之IO操作
- SQL优化清单
- article元素以及section
- Spring cloud 微服务架构 Eureka篇
- linux 解压压缩大全
- 重置Root用户密码
- AjaxControlToolkit的使用
- python 神经网络实例
- 服务器安装Ubuntu的那些坑
- Ruby初探
- Git菜鸟
- Java线程总结(转)
- XSS插入绕过一些方式总结
- Vue 什么是组件