HDU 5695 Gym Class (拓扑排序&贪心）

题意：若干人排队，每人一个权值，给若干优先级顺序，求怎么排队（在特定权值计算下）权值和最大。

思路：贪心思想：在满足优先级的情况下权值越大排在越前面

时间复杂度：O(N+M)

#include<bits/stdc++.h>
using namespace std;
priority_queue<int>q;
const int N=1e5+5;
typedef long long ll;
ll in[N],n,m;
vector<int>v[N];
void init(){
	for(int i=1;i<=n;i++)
		in[i]=0,v[i].clear();
}
ll toposort(){
	ll ans=0,minn=0x3f3f3f3f;
	for(int i=1;i<=n;i++) if(!in[i]) q.push(i);//入度为0的点是排在最前面 
	while(q.size()){//优先队列越大越在前面 因为要是总和最大 所以越大越前面是最优的 
		ll now=q.top();q.pop();
		minn=min(minn,now);//又因为每个答案贡献是最小的那个值，所以就相当于取前面队列的最小值。 
		ans+=minn;
		for(auto i:v[now])
			if(--in[i]==0) q.push(i); 
	}
	return ans; 
}
int main(){
	int t;
	ios::sync_with_stdio(false);cin.tie(0);//当输入超过1e5时 注意关闭流同步 
	cin>>t;
	while(t--){
		cin>>n>>m;
		init();//初始化 
		while(m--){
			int a,b;
			cin>>a>>b;
			v[a].push_back(b);
			in[b]++;
		}
		cout<<toposort()<<endl;
	}
	return 0;
}