浙江财经大学
信工学院ACM集训队

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

本文由 Ocrosoft 于 2016-07-10 15:16:41 发表

确定比赛名次

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 21085    Accepted Submission(s): 8495

Problem 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
 

Author
SmallBeer(CML)
 

Solution

基础的拓扑排序,按着原样写就好了。

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <list>
#include <stack>
#include <string>
#include <vector>
#include <cstring>
#include <cctype>
#include <queue>
#include <set>
#include <climits>
#define ms(a) memset(a,0,sizeof(a))
using namespace std;
template <typename T>
T read(T& t)
{
    cin>>t;
    return t;
}
int n,m,t;//节点(队伍)数量,边(比赛)数量,临时变量
bool mp[505][505];//邻接表保存边信息
int indegree[505];//保存入度
struct cmp//升序排列
{bool operator()(int& a,int& b){return a>b;}};
priority_queue<int,vector<int>,cmp> q;//因为要求从小到大,所以用优先队列。
void toposort()
{
    bool flag=1;//第一个输出的标记
    while(!q.empty())
    {
        t=q.top();
        q.pop();//第一个输出不能输出空格
        printf("%s%d",flag?"":" ",t);
        flag=0;
        for(int i=1; i<=n; i++)//遍历这个节点的邻接表
        {
            if(mp[t][i])//如果找到一条边
            {
                indegree[i]--;//删除边,相应节点入度-1
                if(!indegree[i])q.push(i);//如果入度为0,放入队列
            }
        }
    }
    printf("\n");
}
int main()
{
    while(cin>>n>>m)
    {
        ms(indegree),ms(mp);//清理
        while(!q.empty())q.pop();//清空队列
        for(int i=0; i<m; i++)//读取边,修改入度
        {
            int a,b;
            cin>>a>>b;//如果没有记录过,记录并且入度+1
            if(!mp[a][b])mp[a][b]=1,indegree[b]++;
        }
        for(int i=1; i<=n; i++)//查找入度为0的点
            if(!indegree[i])q.push(i);//放入队列
        toposort();
    }
    return 0;
}

 

欢迎转载,请保留出处与链接。Ocrosoft » HDU 1285 确定比赛名次(拓扑排序)

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址