本文主要是介绍AOV拓扑排序（优先队列） HDU 1285 确定比赛名次，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
确定比赛名次
TimeLimit: 2000/1000 MS (Java/Others) Memory Limit:65536/32768 K (Java/Others)
Total Submission(s): 33731 Accepted Submission(s): 13226
ProblemDescription
有N个比赛队（1<=N<=500），编号依次为1，2，3，。。。。，N进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名，但现在裁判委员会不能直接获得每个队的比赛成绩，只知道每场比赛的结果，即P1赢P2，用P1，P2表示，排名时P1在P2之前。现在请你编程序确定排名。
Input
输入有若干组，每组中的第一行为二个数N（1<=N<=500），M；其中N表示队伍的个数，M表示接着有M行的输入数据。接下来的M行数据中，每行也有两个整数P1，P2表示即P1队赢了P2队。
Output
给出一个符合要求的排名。输出时队伍号之间有空格，最后一名后面没有空格。
其他说明：符合条件的排名可能不是唯一的，此时要求输出时编号小的队伍在前；输入数据保证是正确的，即输入数据确保一定能有一个符合要求的排名。
SampleInput
4 3
1 2
2 3
4 3
SampleOutput
1 2 4 3
Author
SmallBeer(CML)
Source
杭电ACM集训队训练赛（VII）
Recommend
lcy | Wehave carefully selected several similar problems for you: 1233 2647 3342 1811 2066
算法实现：
拓扑排序的经典例子，主要重设数组ans记录答案，这题输出：按从小到大，要优先队列（最小先出来，非递归只能用优先队列），输出格式要注意一下。
代码实现：
#include<bits/stdc++.h>
using namespace std;
#define N 2005
int n,m;
vector<int>g[N];//g[i]表示i节点所指向的其他节点
int in[N]; //节点入读
int topsort()
{priority_queue<int,vector<int>,greater<int> >q;//保证小值先出队列(题目要求没办法）for(int i=1;i<=n;i++)if(in[i]==0)q.push(i);int cnt=0,ans[N];while(!q.empty()){int u=q.top();q.pop();ans[cnt++]=u;for(int i=0;i<g[u].size();i++){int v=g[u][i];if(--in[v]==0)q.push(v);}}printf("%d",ans[0]);//输出要求很严格for(int i=1;i<n;i++)printf(" %d",ans[i]);cout<<endl;}
int main()
{while(scanf("%d%d",&n,&m)!=EOF){memset(in,0,sizeof(in));for(int i=0;i<=n;i++) g[i].clear();for(int i=0;i<m;i++){int u,v;scanf("%d%d",&u,&v);g[u].push_back(v);in[v]++;}topsort();}return 0;
}
这篇关于AOV拓扑排序（优先队列） HDU 1285 确定比赛名次的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
