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

待我称王封你为后i 2023-07-12 14:09 3阅读 0赞

> 原题链接：[http://acm.hdu.edu.cn/showproblem.php?pid=1285][http_acm.hdu.edu.cn_showproblem.php_pid_1285]

**思路：** 拓扑排序裸题，这里用优先队列的做法。拓扑排序就是每次将入度为 0 的数压入队列，优先队列可以使得压入队列的数按编号从小到大排序。

**Code：**

#include <iostream>
    #include <queue>
    #include <cstring>
    using namespace std;
    const int N=505;
    int n,m;
    int e[N][N],pre[N];
    void tuopu(){ 
        priority_queue<int,vector<int>,greater<int> > q;
        for(int i=1;i<=n;i++)
            if(!pre[i]) q.push(i);
        int flag=1;
        while(!q.empty()){ 
            int start = q.top();
            q.pop();
            pre[start]=-1;
            if(flag){ 
                cout<<start;
                flag=0;
            }
            else    cout<<' '<<start;
            for(int i=1;i<=n;i++){ 
                if(e[start][i]){ 
                    pre[i]--;
                    if(!pre[i]) q.push(i);
                }
            }
        }
        cout<<endl;
    }
    int main(){ 
        ios::sync_with_stdio(0);
        while(cin>>n>>m){ 
            memset(e,0,sizeof(e));
            memset(pre,0,sizeof(pre));
            for(int i=0;i<m;i++){ 
                int a,b;    cin>>a>>b;
                if(!e[a][b]){ 
                    e[a][b]=1;
                    pre[b]++;
                }
            }
            tuopu();
        }
        return 0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_1285]: http://acm.hdu.edu.cn/showproblem.php?pid=1285

发表评论取消回复

表情：

评论列表（有 0 条评论，3人围观）

还没有评论，来说两句吧...

相关阅读

相关确定比赛名次拓扑排序 + 优先队列

<table> <tbody> <tr> <td> <h2>确定比赛名次</h2> <strong>Time Limit: 2000/1000 MS (Jav

朱雀/ 2024年02月18日 22:58/ 0 赞/ 85 阅读

相关 HDOJ--1285 确定比赛名次(拓扑排序)

Problem Description 有N个比赛队（1<=N<=500），编号依次为1，2，3，。。。。，N进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名

素颜马尾好姑娘i/ 2023年10月17日 14:33/ 0 赞/ 20 阅读

相关【HDU】1285 - 确定比赛名次（拓扑排序）

> 原题链接：[http://acm.hdu.edu.cn/showproblem.php?pid=1285][http_acm.hdu.edu.cn_showpro

待我称王封你为后i/ 2023年07月12日 14:09/ 0 赞/ 4 阅读

相关拓扑排序学习小记 HDU 1285 确定比赛名次 + HDU 2647 Reward

拓扑排序，以下摘自http://blog.csdn.net/midgard/article/details/4101025：拓扑排序是对有向无环图(DAG图)的一种排序。表

落日映苍穹つ/ 2022年08月25日 08:46/ 0 赞/ 133 阅读

相关杭电-1285确定比赛名次(topo)

确定比赛名次 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Other

今天药忘吃喽~/ 2022年08月10日 08:37/ 0 赞/ 108 阅读

相关 hdoj 1285 确定比赛名次【拓扑】

确定比赛名次 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Ot

秒速五厘米/ 2022年08月04日 13:44/ 0 赞/ 132 阅读

相关确定比赛名次（拓扑排序）

![20150705134445245][] 这一题是典型的拓扑排序题目！需要注意的两点就是可能有重复边，所以你要学会过滤重复边！还有就是定义变量要在main函

清疚/ 2022年08月02日 01:29/ 0 赞/ 186 阅读

相关【杭电1285】确定比赛名次

确定比赛名次 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Other

ゞ浴缸里的玫瑰/ 2022年07月18日 16:24/ 0 赞/ 172 阅读

相关确定比赛名次

确定比赛名次有N个比赛队（1<=N<=500），编号依次为1，2，3，。。。。，N进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名，但现在裁判委员会不能

男娘i/ 2022年05月15日 05:58/ 0 赞/ 184 阅读

相关杭电 1285 确定比赛名次（直接拓扑排序）

Problem Description 有N个比赛队（1<=N<=500），编号依次为1，2，3，。。。。，N进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次

绝地灬酷狼/ 2021年12月20日 08:55/ 0 赞/ 171 阅读