当前位置：网站首页>hdu 1285 确定比赛名次(拓扑排序)

hdu 1285 确定比赛名次(拓扑排序)

2022-08-09 18:35:00 【51CTO】

题目： http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=30402

Description

有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

给出一个符合要求的排名。输出时队伍号之间有空格，最后一名后面没有空格。

其他说明：符合条件的排名可能不是唯一的，此时要求输出时编号小的队伍在前；输入数据保证是正确的，即输入数据确保一定能有一个符合要求的排名。

Sample Input

4 3 1 2 2 3 4 3

Sample Output

1 2 4 3

我一般不找失败的借口，但是这题真是前辈误导了我 ||- _ - 听说要用优先队列，我啪啦啪啦敲完后发现和题里例子都对不上。优先级的问题都未能很好解决，怎么能用优先队列呢？比如用例，1-->2-->3<--4。在拓扑排序完成后，1和4是同一级的，所以结果该是1 4 2 3。sigh~以后想好再敲。

为逝去的代码默哀3分钟：

WA：

       
       #include <iostream>
       
       #include <cstdio>
       
       #include <queue>
       
       #include <cstring>
       
       #include <vector>
       
       using 
       
       namespace 
       
       std;
       
       const 
       
       int 
       
       maxn
       
       =
       
       5e2
       
       +
       
       5;
       
       struct 
       
       node{
       
       int 
       
       to,
       
       next;
       
}
       
       edge[
       
       maxn];
       
       int 
       
       head[
       
       maxn],
       
       indegree[
       
       maxn],
       
       n,
       
       m;
       
       struct 
       
       team{
       
       int 
       
       dex,
       
       clas;
       
}
       
       t[
       
       maxn];
       
       int 
       
       iq;
       
       void 
       
       topsort(){
       
       int 
       
       i,
       
       k,
       
       cla
       
       =
       
       1;
       
       int 
       
       que[
       
       maxn];
       
       iq
       
       =
       
       0;
       
       for(
       
       i
       
       =
       
       1;
       
       i
       
       <=
       
       n;
       
       i
       
       ++){
       
       if(
       
       indegree[
       
       i]
       
       ==
       
       0) {
       
       t[
       
       iq].
       
       dex
       
       =
       
       i;
       
       t[
       
       iq].
       
       clas
       
       =
       
       cla;
       
       que[
       
       iq
       
       ++]
       
       =
       
       i;
       
         }
       
     }
       
       cla
       
       ++;
       
       for(
       
       i
       
       =
       
       0;
       
       i
       
       <
       
       iq;
       
       i
       
       ++){
       
       bool 
       
       jia
       
       =
       
       0;
       
       for(
       
       k
       
       =
       
       head[
       
       que[
       
       i]];
       
       k
       
       >
       
       0;
       
       k
       
       =
       
       edge[
       
       k].
       
       next){
       
       indegree[
       
       edge[
       
       k].
       
       to]
       
       --;
       
       if(
       
       indegree[
       
       edge[
       
       k].
       
       to]
       
       ==
       
       0){
       
       t[
       
       iq].
       
       dex
       
       =
       
       edge[
       
       k].
       
       to;
       
       t[
       
       iq].
       
       clas
       
       =
       
       cla;
       
       que[
       
       iq
       
       ++]
       
       =
       
       edge[
       
       k].
       
       to;
       
       jia
       
       =
       
       1;
       
             }
       
         }
       
       if(
       
       jia)
       
       cla
       
       ++;
       
     }
       
}
       
       struct 
       
       cmp{
       
       bool 
       
       operator()(
       
       team 
       
       a,
       
       team 
       
       b){
       
       if(
       
       a.
       
       clas
       
       !=
       
       b.
       
       clas)
       
       return 
       
       a.
       
       clas
       
       >
       
       b.
       
       clas;
       
       return 
       
       a.
       
       dex
       
       >
       
       b.
       
       dex;
       
    }
       
};
       
       int 
       
       main()
       
{
       
       freopen(
       
       "cin.txt",
       
       "r",
       
       stdin);
       
       int 
       
       a,
       
       b;
       
       while(
       
       cin
       
       >>
       
       n
       
       >>
       
       m){
       
       memset(
       
       head,
       
       0,
       
       sizeof(
       
       head));
       
       memset(
       
       indegree,
       
       0,
       
       sizeof(
       
       indegree));
       
       memset(
       
       edge,
       
       0,
       
       sizeof(
       
       edge));
       
       for(
       
       int 
       
       i
       
       =
       
       1;
       
       i
       
       <=
       
       m;
       
       i
       
       ++){
       
       scanf(
       
       "%d %d",
       
       &
       
       a,
       
       &
       
       b);
       
       edge[
       
       i].
       
       to
       
       =
       
       b;
       
       edge[
       
       i].
       
       next
       
       =
       
       head[
       
       a];
       
       head[
       
       a]
       
       =
       
       i;
       
       indegree[
       
       b]
       
       ++;
       
        }
       
       topsort();
       
       priority_queue
       
       <
       
       team,
       
       vector
       
       <
       
       team
       
       >,
       
       cmp 
       
       > 
       
       qq;
       
       for(
       
       int 
       
       i
       
       =
       
       0;
       
       i
       
       <
       
       iq;
       
       i
       
       ++){
       
       qq.
       
       push(
       
       t[
       
       i]);
       
        }
       
       int 
       
       ans;
       
       while(
       
       !
       
       qq.
       
       empty()){
       
       ans
       
       =
       
       qq.
       
       top().
       
       dex;
       
       qq.
       
       pop();
       
       if(
       
       qq.
       
       empty()) 
       
       break;
       
       printf(
       
       "%d ",
       
       ans);
       
        }
       
       printf(
       
       "%d\n",
       
       ans);
       
    }
       
       return 
       
       0;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.

不用优先队列，直接在遍历时就控制大小：

AC:

       
       #include <iostream>
       
       #include <cstdio>
       
       #include <cstring>
       
       using 
       
       namespace 
       
       std;
       
       const 
       
       int 
       
       maxn
       
       =
       
       5e2
       
       +
       
       5;
       
       int 
       
       map[
       
       maxn][
       
       maxn],
       
       indegree[
       
       maxn],
       
       n,
       
       m;
       
       void 
       
       topsort(){
       
       for(
       
       int 
       
       i
       
       =
       
       1;
       
       i
       
       <=
       
       n;
       
       i
       
       ++){
       
       for(
       
       int 
       
       j
       
       =
       
       1;
       
       j
       
       <=
       
       n;
       
       j
       
       ++){
       
       if(
       
       indegree[
       
       j]
       
       ==
       
       0){
       
       indegree[
       
       j]
       
       --;
       
       if(
       
       i
       
       !=
       
       n) 
       
       cout
       
       <<
       
       j
       
       <<
       
       " ";
       
       else 
       
       cout
       
       <<
       
       j
       
       <<
       
       endl;
       
       for(
       
       int 
       
       k
       
       =
       
       1;
       
       k
       
       <=
       
       n;
       
       k
       
       ++){
       
       if(
       
       map[
       
       j][
       
       k]
       
       ==
       
       1){
       
       indegree[
       
       k]
       
       --;
       
                    }
       
                }
       
       break;
       
            }
       
        }
       
    }
       
}
       
       int 
       
       main()
       
{
       
       //freopen("cin.txt","r",stdin);
       
       int 
       
       a,
       
       b;
       
       while(
       
       cin
       
       >>
       
       n
       
       >>
       
       m){
       
       memset(
       
       map,
       
       0,
       
       sizeof(
       
       map));
       
       memset(
       
       indegree,
       
       0,
       
       sizeof(
       
       indegree));
       
       for(
       
       int 
       
       i
       
       =
       
       0;
       
       i
       
       <
       
       m;
       
       i
       
       ++){
       
       scanf(
       
       "%d %d",
       
       &
       
       a,
       
       &
       
       b);
       
       if(
       
       !
       
       map[
       
       a][
       
       b]){
       
       map[
       
       a][
       
       b]
       
       =
       
       1;
       
       indegree[
       
       b]
       
       ++;
       
            }
       
        }
       
       topsort();
       
    }
       
       return 
       
       0;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://blog.51cto.com/u_15746559/5560565

当前位置：网站首页>hdu 1285 确定比赛名次(拓扑排序)

hdu 1285 确定比赛名次(拓扑排序)

边栏推荐

猜你喜欢

随机推荐