题解

这题可以使用拓扑排序的方法解决。
首先把没有直接先修课的课程加入优先队列，然后每次挑最大值广搜即可。

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
int a[100005], b[100005];
vector <int> v[100005];
bool vis[100005];
priority_queue <pair <int, int>> q;
int main(){
	cin.tie(nullptr) -> sync_with_stdio(0);
	cout.tie(nullptr) -> sync_with_stdio(0);
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		cin >> b[i] >> a[i];
		if(!b[i]) q.push({a[i], i});//没有先修课的加入
		else v[b[i]].push_back(i);//连边
	}
	int ct = 0, ctt = 0;
	while(!q.empty() && ctt < m){
		auto head = q.top();//取最大值
		q.pop();
		ct += head.first, ctt++;
		for(int i:v[head.second]){
			if(!vis[i]) vis[i] = 1, q.push({a[i], i});//加入有当前课程作为先修课的课程
		}
	}
	cout << ct;

	return 0;
}

时间复杂度：$O(M\log N)$。