hdu5695 拓扑排序（模板）
发布时间：2020-12-15 08:02:03 所属栏目：Java 来源：网络整理
导读：?Problem Description 众所周知，度度熊喜欢各类体育活动。 今天，它终于当上了梦寐以求的体育课老师。第一次课上，它发现一个有趣的事情。在上课之前，所有同学要排成一列， 假设最开始每个人有一个唯一的ID，从1到 N ，在排好队之后，每个同学会找出包括自
|
?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
? ? tips：ans会爆int！ #include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
vector<int> s[maxn];
int ind[maxn],vis[maxn];
int n,m;
void init(){
memset(ind,sizeof(ind));
memset(vis,sizeof(vis));
for(int i=0;i<=n;i++)
s[i].clear();
}
void toop(){
ll ans=0;
ll minn=inf;
priority_queue< int,vector< int >,less<int> >q;
for(int i=1;i<=n;i++){
if(ind[i]==0){
q.push(i);
vis[i]=1;
}
}
while(q.size() ){
ll u=q.top();
q.pop();
minn=min( minn,u);
ans+=minn;
for(int i=0;i<s[u].size();i++){
int v=s[u][i];
ind[v]--;
if(ind[v]==0&&!vis[v]) {
q.push(v);
vis[v]=1;
}
}
}
printf("%lldn",ans);
}
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
init();
for(int i=0;i<m;i++){
int a,b;
scanf("%d%d",&a,&b);
ind[b]++;
s[a].push_back(b);
}
toop();
}
return 0;
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |