Gym Class
Time Limit: 6000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 681 Accepted Submission(s): 271
Problem Description
众所周知，度度熊喜欢各类体育活动。
今天，它终于当上了梦寐以求的体育课老师。第一次课上，它发现一个有趣的事情。在上课之前，所有同学要排成一列， 假设最开始每个人有一个唯一的ID，从1到N
，在排好队之后，每个同学会找出包括自己在内的前方所有同学的最小ID，作为自己评价这堂课的分数。麻烦的是，有一些同学不希望某个（些）同学排在他（她）前面，在满足这个前提的情况下，新晋体育课老师——度度熊，希望最后的排队结果可以使得所有同学的评价分数和最大。
Input
第一行一个整数T
，表示T(1≤T≤30)
组数据。
对于每组数据，第一行输入两个整数N
和M(1≤N≤100000,0≤M≤100000)
，分别表示总人数和某些同学的偏好。
接下来M
行，每行两个整数A
和B(1≤A,B≤N)
，表示ID为A
的同学不希望ID为B
的同学排在他（她）之前。你可以认为题目保证至少有一种排列方法是符合所有要求的。
Output
对于每组数据，输出最大分数 。
Sample Input
3
1 0
2 1
1 2
3 1
3 1
Sample Output
1
2
6
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#define ll __int64
using namespace std;
vector<int> mp[];
int in[];
int t;
int ans[];
int vis[];
struct node
{
int x;
friend bool operator < (node aa,node bb)
{
return aa.x<bb.x;
}
};
priority_queue<node> p;
int n,m,a,b;
int main()
{
while(scanf("%d",&t)!=EOF)
{
for(int i=;i<=t;i++)
{
scanf("%d %d",&n,&m);
int jishu=;
struct node exm;
memset(ans,,sizeof(ans));
for(int j=;j<=n;j++)
{
mp[j].clear();
in[j]=;
vis[j]=;
}
for(int j=;j<=m;j++)
{
scanf("%d %d",&a,&b);
mp[a].push_back(b);
in[b]++;
}
for(int j=;j<=n;j++)
{
if(in[j]==)
{
exm.x=j;
vis[j]=;
p.push(exm);
}
}
while(!p.empty())
{
exm=p.top();
ans[jishu++]=exm.x;
p.pop();
for(unsigned int j=;j<mp[exm.x].size();j++)
{
if(--in[mp[exm.x][j]]==&&vis[mp[exm.x][j]]==)
{
vis[mp[exm.x][j]]==;
struct node ggggg;////wa点
ggggg.x=mp[exm.x][j];
p.push(ggggg);
}
}
}
int minx=ans[];
ll gg=ans[];
for(int j=;j<=n;j++)
{
minx=min(minx,ans[j]);
gg+=minx;
}
printf("%I64d\n",gg);
}
}
return ;
}