问题描述:
有一天,TT 在 B 站上观看猫猫的比赛。一共有 N 只猫猫,编号依次为1,2,3,…,N进行比赛。比赛结束后,Up 主会为所有的猫猫从前到后依次排名并发放爱吃的小鱼干,TT 的魔法猫将每场比赛的结果都记录了下来,现在他想编程序确定字典序最小的名次序列,请你帮帮他。
input:
输入有若干组,每组中的第一行为二个数N(1<=N<=500),M;其中N表示猫猫的个数,M表示接着有M行的输入数据。接下来的M行数据中,每行也有两个整数P1,P2表示即编号为 P1 的猫猫赢了编号为 P2 的猫猫。
output:
给出一个符合要求的排名。输出时猫猫的编号之间有空格,最后一名后面没有空格!
其他说明:符合条件的排名可能不是唯一的,此时要求输出时编号小的队伍在前;输入数据保证是正确的,即输入数据确保一定能有一个符合要求的排名。
样例输入:
4 3
1 2
2 3
4 3
样例输出:
1 2 4 3
解题思路:
在这个问题中,猫猫们的比赛胜负关系可以等价为一个有向图,a赢了b表示有一条边从a指向b,并且最终的名次a在b的前面。如果两个猫的名次相同,则字典序小的那个排在前面。那么该问题就可以转化为求字典序最小的拓扑序列。为了保证字典序最小,我们可以将放入队列中的点放入一个优先级队列中,由于priority_queue默认是最大堆,则我们可以将节点的负值放进去,从而相当于最小堆。
在实现时,首先将图中所有的边加入,在加入的同时,利用一个数组来记录每一个点的出度。在构造完成之后,入过某些点的出度为0,那么它的名次就靠前,就可以放入到优先级队列中,如果队列不空,从队列中取出最小值的负值,将其所有的邻接边删除,并判断是否有点的入度为0,如果有的话,加入优先级队列中,重复此过程。最终得到一个字典序最小的排名。
代码:
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int N,M;
int a[510];
vector<int> b[510];
int main()
{
while(cin>>N>>M)
{
for(int i=1;i<=N;i++)
{
a[i]=0;
b[i].clear();
}
priority_queue<int> p;
vector<int> end;
for(int i=0;i<M;i++)
{
int x,y;
cin>>x>>y;
a[y]++;
b[x].push_back(y);
}
for(int i=1;i<=N;i++)
{
if(a[i]==0)
p.push(-i);
}
while(!p.empty())
{
int te=-p.top();
p.pop();
end.push_back(te);
for(int i=0;i<b[te].size();i++)
{
int tt=b[te][i];
a[tt]--;
if(a[tt]==0)
p.push(-tt);
}
}
for(int i=0;i<end.size();i++)
{
cout<<end[i];
if(i!=end.size()-1)
cout<<" ";
}
cout<<endl;
}
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)