锐客网

  1. 首页 > 睿知 > it技术 > >

HDU - 1285确定比赛名次 （拓扑排序）

IT知识排序拓扑排序

弱龄寄事外，委怀在琴书。这篇文章主要讲述HDU - 1285确定比赛名次 （拓扑排序）相关的知识，希望能为你提供帮助。
题干：
有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
给出一个符合要求的排名。输出时队伍号之间有空格，最后一名后面没有空格。 

其他说明：符合条件的排名可能不是唯一的，此时要求输出时编号小的队伍在前；输入数据保证是正确的，即输入数据确保一定能有一个符合要求的排名。 
【HDU - 1285确定比赛名次 （拓扑排序）】Sample Input

4 3
1 2
2 3
4 3

Sample Output
1 2 4 3

解题报告：
    拓扑排序模板。用邻接矩阵存图，会超时。
 
  AC代码：
#include< bits/stdc++.h>

using namespace std;
const int MAX = 500 + 5 ;
struct Node
int to;
int w;
int ne;
e[MAX];
int in[MAX],head[MAX],ans[MAX];
int cnt = 0,top = 0;
priority_queue< int,vector< int > ,greater< int> > pq;
void init()
cnt = 0; top = 0;
memset(in,0,sizeof(in));
memset(head,-1,sizeof(head));
while(!pq.empty() ) pq.pop();

void add(int u,int v,int w)
e[cnt].to = v;
e[cnt].w = w;
e[cnt].ne = head[u];
head[u] = cnt;
cnt++;

int main()

int n,m;
int u,v;
while(~scanf("%d%d",& n,& m) )
init();
while(m--)
scanf("%d%d",& u,& v);
add(u,v,0);
in[v]++;

//预处理一下pq
for(int i = 1; i< =n; i++)
if(in[i] == 0 ) pq.push(i);

while(!pq.empty() )
int cur = pq.top(); //养成习惯，bfs中也是，取出元素后都先给一个变量cur存着以免以后忘了pop，并且新的都用new表示
pq.pop();
ans[++top] = cur;
for(int i = head[cur]; i!=-1; i=e[i].ne)
in[e[i].to]--;
if(in[e[i].to] == 0) pq.push(e[i].to);


if(top != n ) printf("不成环\\n");
else
for(int i = 1; i< =top; i++)
printf("%d%c",ans[i],i==top?\\n: );





return 0 ;

超时代码：
#include< iostream>
#include< cstdio>
#include< cstring>
using namespace std;
//struct Edge
//int to;
//int w;
//int ne;
//
// e[5000];
int maze[505][505];
int in[505];
void init()
memset(in,0,sizeof(in));
memset(maze,0,sizeof(maze) ) ;

int main()

int n,m,u,v;
int flag = 0;
while(~scanf("%d%d",& n,& m) )
init();
while(m--)
scanf("%d%d",& u,& v);
maze[u][v] = 1;
in[v]++;

int cnt = 0 ;
while(1)

if(cnt == n) break;
flag = 0 ;
for(int i = 1; i< =n; i++)
if(in[i] == 0)
in[i]--;
if(cnt == n-1)
printf("%d\\n",i);
cnt++;

for(int j

    推荐阅读


    上一篇：POJ - 1789ZOJ - 2158SCU - 1832Truck History （最小生成树）

    下一篇：[ C++ ] 类与对象(下) 初始化列表，友元，static成员，内部类