題意：有N個比賽隊（1<=N<=500），編號依次為1，2，3，。。。。，N進行比賽，比賽結束后，裁判委員會要將所有參賽隊伍從前往后依次排名，但現在裁判委員會不能直接獲得每個隊的比賽成績，只知道每場比賽的結果，即P1贏P2，用P1，P2表示，排名時P1在P2之前。現在請你編程序確定排名。 （中文題面就不講了）

主這題需要按字典序最小來排序，所以用優先隊列代替隊列完成拓撲排序就行。

1 #include<stdio.h> 2 #include<string.h> 3 #include<queue> 4 #include<algorithm> 5 using namespace std; 6 const int maxm=505; 7 8 int id[maxm],n,m; 9 int ma[maxm][maxm]; 10 11 void topo(){ 12 priority_queue<int,vector<int>,greater<int> >q; 13 for(int i=1;i<=n;i++){ 14 if(!id[i])q.push(i); 15 } 16 int cnt=0; 17 while(!q.empty()){ 18 int u=q.top(); 19 printf("%d",u); 20 if(++cnt==n)printf("\n"); 21 else printf(" "); 22 q.pop(); 23 for(int i=1;i<=n;++i){ 24 if(i==u)continue; 25 if(ma[u][i]){ 26 id[i]--; 27 if(!id[i])q.push(i); 28 } 29 } 30 } 31 } 32 33 int main(){ 34 while(scanf("%d%d",&n,&m)!=EOF){ 35 memset(ma,0,sizeof(ma)); 36 while(m--){ 37 int a,b; 38 scanf("%d%d",&a,&b); 39 if(!ma[a][b]){ 40 ma[a][b]=1; 41 id[b]++; 42 } 43 } 44 topo(); 45 } 46 return 0; 47 } View Code

?

轉載于:https://www.cnblogs.com/cenariusxz/p/4794883.html

總結

以上是生活随笔為你收集整理的hdu1285 拓扑序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。