题意:众所周知,度度熊喜欢各类体育活动。
今天,它终于当上了梦寐以求的体育课老师。第一次课上,它发现一个有趣的事情。在上课之前,所有同学要排成一列, 假设最开始每个人有一个唯一的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 }