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;
}