AOV拓扑排序（优先队列） HDU 1285 确定比赛名次

本文主要是介绍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 确定比赛名次的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---