﻿HDU 5695 Gym Class(拓扑排序)-Ocrosoft

# Gym Class

Time Limit: 6000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 911    Accepted Submission(s): 373

Problem Description

Input

Output

Sample Input


3
1 0
2 1
1 2
3 1
3 1



Sample Output


1
2
6



Solution

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ms(a) memset(a,0,sizeof(a))
#define INF INT_MAX
#define MAXN 1000+10
using namespace std;
int n,m,t,tt;
vector<int> v[100001];
int in[100001];
vector<int> ans;
priority_queue<int> q;//默认取出最大
void toposort()
{
ans.clear();
while(!q.empty())
{
t=q.top(),q.pop();
ans.push_back(t);
for(int i=0,vs=v[t].size(); i<vs; i++)
{
in[v[t][i]]--;
if(!in[v[t][i]])q.push(v[t][i]);
}
}
long long sum = 0, Min = 1000000;
for (int i = 0; i < n; i++)
{
Min = min (Min, 1LL*ans[i]);
sum += Min;
}
printf("%lld\n",sum);
}
int main()
{
int N;
cin>>N;
while(N--)
{
cin>>n>>m;
ms(in);
for(int i=1; i<=n; i++)v[i].clear(); //清空要用的数组
//u不希望v排在前面，就是u有一条边指向v
for(int i=0; i<m; i++)
scanf("%d%d",&t,&tt),v[t].push_back(tt),in[tt]++;
for(int i=1; i<=n; i++)if(!in[i])q.push(i);
toposort();
}
return 0;
}