Gym Class HDU - 5695

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

思路:将入度为0的点放在最前面,之后拓扑排序删除与之有关边的入度,利用优先权队列可以自动排序,每次取出对顶元素。

注意这里的n是1e5,不能实现矩阵,只能用一维数组和结构体描述

此次还有重大发现!!!上次一直tl原因是我的输入都写得cin,用scanf就可过!原因是cin会先先把输入放置在缓冲区,满了才输出刷新

scanf是格式化输入,printf是格式化输出。格式化输出效率比较高,但是写代码麻烦。具体链接:https://blog.csdn.net/deng529828/article/details/6173655


 1 #include<iostream>
 2 #include<algorithm>
 3 #include<queue>
 4 #include<cstring>
 5 using namespace std;
 6 typedef long long ll;
 7 int T, n, m, a, b;
 8 int head[100100];
 9 struct node {
10     int to;
11     int next;
12 }p[100100];
13 int rudu[100100];
14 int main() {
15     scanf("%d", &T);
16     while (T--) {
17         scanf("%d%d", &n, &m);
18         for (int i = 1; i <= n; i++){
19             head[i] = -1;
20             rudu[i] = 0;
21         }
22         while (m--) {
23             scanf("%d%d", &a, &b);
24             p[m].to = b;
25             p[m].next = head[a];
26             head[a] = m;
27             rudu[b]++;
28         }
29         priority_queue<int> que;
30         for (int i = 1; i <= n; i++) 
31             if (rudu[i] == 0) 
32                 que.push(i);        
33         ll ans = 0;
34         int lp = 120000000;
35         while (!que.empty()) {
36             int fr = que.top();
37             que.pop();
38             lp = min(lp, fr);
39             ans += lp;
40             for (int j = head[fr]; j != -1; j = p[j].next) {
41                 int d = p[j].to;
42                 rudu[d]--;
43                 if (rudu[d] == 0) {
44                     que.push(d);
45                 }
46             }
47         }
48         printf("%I64d\n", ans);
49     }
50     return 0;
51 }

 

上一篇:20174304王天政《网络对抗技术》Exp6 MSF基础应用


下一篇:用了这个功能会让您的CS性能更好,运行更稳