題目鏈接：acm.hdu.edu.cn/showproblem.php?pid=5695

Problem Description

眾所周知，度度熊喜歡各類體育活動(dòng)。
今天，它終于當(dāng)上了夢(mèng)寐以求的體育課老師。第一次課上，它發(fā)現(xiàn)一個(gè)有趣的事情。在上課之前，所有同學(xué)要排成一列， 假設(shè)最開始每個(gè)人有一個(gè)唯一的ID，從1到N，在排好隊(duì)之后，每個(gè)同學(xué)會(huì)找出包括自己在內(nèi)的前方所有同學(xué)的最小ID，作為自己評(píng)價(jià)這堂課的分?jǐn)?shù)。麻煩的是，有一些同學(xué)不希望某個(gè)（些）同學(xué)排在他（她）前面，在滿足這個(gè)前提的情況下，新晉體育課老師——度度熊，希望最后的排隊(duì)結(jié)果可以使得所有同學(xué)的評(píng)價(jià)分?jǐn)?shù)和最大。

Input

第一行一個(gè)整數(shù)T，表示T(1≤T≤30)?組數(shù)據(jù)。
對(duì)于每組數(shù)據(jù)，第一行輸入兩個(gè)整數(shù)N和M(1≤N≤100000,0≤M≤100000)，分別表示總?cè)藬?shù)和某些同學(xué)的偏好。
接下來M行，每行兩個(gè)整數(shù)A?和B(1≤A,B≤N)，表示ID為A的同學(xué)不希望ID為B的同學(xué)排在他（她）之前。你可以認(rèn)為題目保證至少有一種排列方法是符合所有要求的。

Output

對(duì)于每組數(shù)據(jù)，輸出最大分?jǐn)?shù) 。

Sample Input

3 1 0 2 1 1 2 3 1 3 1

Sample Output

1 2 6 解題思路：要使得所有同學(xué)的評(píng)價(jià)分?jǐn)?shù)和最大，必須每次拓?fù)涑鲎畲蟮膇d值（采用優(yōu)先隊(duì)列最大堆來實(shí)現(xiàn)），再保存當(dāng)前已拓?fù)涞淖钚d即為隊(duì)列中后面學(xué)生的課堂分?jǐn)?shù)，并且把每次分?jǐn)?shù)相加起來即為評(píng)價(jià)的總分?jǐn)?shù)，水過！ AC代碼： 1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 const int maxn=100005; 5 vector<int> vec[maxn]; 6 priority_queue<int> que;//默認(rèn)最大堆,id越靠前的最后的評(píng)價(jià)分?jǐn)?shù)將會(huì)是最大的 7 int t,n,m,a,b,minid,InDeg[maxn];LL sum;bool flag; 8 void topsort(){ 9 while(!que.empty())que.pop();//清空隊(duì)列 10 for(int i=1;i<=n;++i) 11 if(!InDeg[i])que.push(i); 12 flag=false; 13 while(!que.empty()){ 14 int now=que.top();que.pop();//取出當(dāng)前最大的id，并且出隊(duì) 15 if(!flag){minid=now;flag=true;}//開關(guān)：記錄第一個(gè)拓?fù)涞膇d值 16 minid=min(minid,now);sum+=minid;//每次更新最小的id，并且加入到sum當(dāng)中 17 for(size_t i=0;i<vec[now].size();++i)//更新每個(gè)鄰接點(diǎn)的入度數(shù) 18 if(--InDeg[vec[now][i]]==0)que.push(vec[now][i]); 19 } 20 } 21 int main(){ 22 scanf("%d",&t); 23 while(t--){ 24 scanf("%d%d",&n,&m);sum=0; 25 memset(InDeg,0,sizeof(InDeg)); 26 for(int i=1;i<=n;++i)vec[i].clear();//每個(gè)鄰接矩陣連接對(duì)應(yīng)清空 27 while(m--){ 28 scanf("%d%d",&a,&b); 29 vec[a].push_back(b);//鄰接表：a指向b 30 InDeg[b]++;//b的入度加1 31 } 32 topsort();printf("%lld\n",sum); 33 } 34 return 0; 35 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/acgoto/p/9313373.html

總結(jié)

以上是生活随笔為你收集整理的题解报告：hdu 5695 Gym Class（拓扑排序）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。