hdu 5695 Gym Class (拓扑排序)

el/2024/7/17 3:06:35

https://vjudge.net/problem/387991/origin

众所周知,度度熊喜欢各类体育活动。 

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

Input

第一行一个整数TT,表示T(1≤T≤30)T(1≤T≤30) 组数据。 

对于每组数据,第一行输入两个整数NN和M(1≤N≤100000,0≤M≤100000)M(1≤N≤100000,0≤M≤100000),分别表示总人数和某些同学的偏好。 

接下来MM行,每行两个整数AA 和B(1≤A,B≤N)B(1≤A,B≤N),表示ID为AA的同学不希望ID为BB的同学排在他(她)之前。你可以认为题目保证至少有一种排列方法是符合所有要求的。 

Output

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

Sample Input

3
1 0
2 1
1 2
3 1
3 1

Sample Output

1
2
6

满足条件下, 从大到小排序是最优解

#include <bits/stdc++.h> 
using namespace std;const int M = 100005;
const int inf = numeric_limits<int>::max();
priority_queue<int> Q;//从大到小的优先队列
vector<int> V[M];//存储边
int n, m, a, b, in[M];//in存储入度 void init()
{for(int i = 1; i <= n; i++) V[i].clear();while(!Q.empty()) Q.pop();memset(in, 0, sizeof in);
}long long toposort()
{long long res = 0; //不用longlong 会WA int mix = inf;for(int i=1;i<=n;i++)//将所有入度为0的顶点放入序列 if(!in[i]) Q.push(i);while(!Q.empty()){int x=Q.top(); Q.pop();mix = min(mix, x);res += (long long)mix;for(int i : V[x])//删除所有与x顶点有关的边 {in[i]--;if(in[i] == 0) //入度为0 Q.push(i);}}return res;
}int main()
{ios::sync_with_stdio(false); //不写会TLE int T;cin >> T;while(T--){cin >> n >> m;init();while(m--){cin >> a >> b;in[b]++;V[a].push_back(b);}cout << toposort() << endl;}return 0;
}

 


http://www.ngui.cc/el/3419444.html

相关文章

hud 5689 瞬间移动(组合数+逆元)

http://acm.hdu.edu.cn/showproblem.php?pid5698 有一个无限大的矩形&#xff0c;初始时你在左上角&#xff08;即第一行第一列&#xff09;&#xff0c;每次你都可以选择一个右下方格子&#xff0c;并瞬移过去&#xff08;如从下图中的红色格子能直接瞬移到蓝色格子&#xf…

多态中成员变量的使用

Dog 继承 Animal 类&#xff0c; 多态中成员变量没有重写。

Java之数据结构

前言 Java工具包提供了强大的数据结构。在Java中的数据结构主要包括以下几种接口和类&#xff1a; 枚举&#xff08;Enumeration&#xff09;位集合&#xff08;BitSet&#xff09;向量&#xff08;Vector&#xff09;栈&#xff08;Stack&#xff09;字典&#xff08;Dictio…

各种办法解决IntelliJ IDEA控制台输出中文乱码问题

output输出乱码 试了网上很多办法 网上流行的方法&#xff1a;https://blog.csdn.net/liu865033503/article/details/81094575 都没有解决&#xff01;&#xff01;&#xff01; 重点要在 也有可能是c盘下的C:\Users\你自己的用户名\.IntelliJIdea2019.1\config配置下还有一…

IDEA 显示Cannot resolve plugin org.apache.maven.plugins:maven-site-plugin:3.3

今天将IntellIJ IDEA 关于Maven的配置总结一下&#xff0c;方便以后可参考。 一.配置Maven环境 前提是jdk环境变量已经配置好 1.下载apache-maven文件&#xff0c;选择自己需要的版本&#xff0c;地址&#xff1a; http://maven.apache.org/download.cgi 2.解压下载文件&…

javaweb项目前端找不到后台servlet解决办法

原因是注解里面没加 urlPatterns"/XXXXX" servlet必须是3.0以上 成功运行&#xff1a;

实现简单的用户名校验,是否存在(ajax)

实现百度注册框的用户名校验功能&#xff1a; 在输入框内输入一个用户名&#xff0c;如果此用户名存在&#xff0c;则红色显示一段文字&#xff0c;否则绿色显示 用的是Jquery和jackson 目录结构&#xff1a; 前端index.html: <!DOCTYPE html> <html lang"en&…

ccf 201909-2 小明种苹果(续)

#include<bits/stdc.h> using namespace std;bool vis[20005]; //第i棵树是否掉过苹果 int main() {long n, ans_sum 0, ans_has 0, ans_con 0;cin >> n;for(int i 1; i < n; i){int start, m, x;bool flag true;cin >> m >> start;for(int j…

const位置的含义

int num 1024; const int num2 num1; //只能第一次赋值 num2 2048 // 报错const int * p &num; //const 在 * 前面时&#xff0c;指针的位置可以修改&#xff0c;但不能通过指针修改指向的变量 int const * p &num; //同上 int * const p &num;//const 在 …

武林秘籍

面向对象&#xff08;一&#xff09;----类的基础语法 &#xff1a; 第1关&#xff1a;类的声明与定义 # 请在下面填入定义Book类的代码 #********** Begin *********# class Book: #********** End *********## 书籍类def __init__(self,name,author,data,version):self.nam…