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

朱雀 2024-02-18 22:58 85阅读 0赞

<table> 
 <tbody> 
 <tr> 
 <td> <h2>确定比赛名次</h2> Time Limit: 2000/1000 MS (Java/Others)&nbsp;&nbsp;&nbsp;&nbsp;Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 36643&nbsp;&nbsp;&nbsp;&nbsp;Accepted Submission(s): 14326 &nbsp; Problem Description 有N个比赛队（1&lt;=N&lt;=500），编号依次为1，2，3，。。。。，N进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名，但现在裁判委员会不能直接获得每个队的比赛成绩，只知道每场比赛的结果，即P1赢P2，用P1，P2表示，排名时P1在P2之前。现在请你编程序确定排名。 &nbsp; &nbsp; Input 输入有若干组，每组中的第一行为二个数N（1&lt;=N&lt;=500），M；其中N表示队伍的个数，M表示接着有M行的输入数据。接下来的M行数据中，每行也有两个整数P1，P2表示即P1队赢了P2队。 &nbsp; &nbsp; Output 给出一个符合要求的排名。输出时队伍号之间有空格，最后一名后面没有空格。 其他说明：符合条件的排名可能不是唯一的，此时要求输出时编号小的队伍在前；输入数据保证是正确的，即输入数据确保一定能有一个符合要求的排名。 &nbsp; &nbsp; Sample Input <pre>&nbsp;</pre> 4 3 1 2 2 3 4 3 &nbsp; &nbsp; Sample Output <pre>&nbsp;</pre> 1 2 4 3 &nbsp; &nbsp; Author SmallBeer(CML) &nbsp; &nbsp; Source </td> 
 </tr> 
 </tbody> 
</table>

重点：符合条件的排名可能不是唯一的，此时要求输出时编号小的队伍在前；用一个·优先队列存入度为零的点，先处理度为零而且小的点，就解决了这个问题。

\#include<iostream> 
\#include<algorithm> 
\#include<cstdlib> 
\#include<string.h> 
\#include<queue> 
\#include<vector> 
using namespace std; 
int n,m,map\[501\]\[501\],in\[501\],a\[501\]; 
void tpsort() 
\{ 
int t,cnt=1,i,j; 
priority\_queue<int,vector<int>,greater<int> > q; 
for(i=1; i<=n; i++) 
\{ 
if(in\[i\]==0) 
\{ 
 
q.push(i); 
\} 
 
\} 
 
while(!q.empty()) 
\{ 
t=q.top(); 
a\[cnt++\]=t; 
q.pop(); 
for(j=1; j<=n; j++) 
\{ 
if(map\[t\]\[j\]) 
\{ 
in\[j\]--; 
if(in\[j\]==0) 
q.push(j); 
\} 
\} 
\} 
for(i=1; i<n; i++) 
printf("%d ",a\[i\]); 
printf("%d\\n",a\[n\]);

\} 
int main() 
\{ 
int i,j,u,v; 
while(~scanf("%d%d",&n,&m)) 
\{ 
memset(in,0,sizeof(in)); 
memset(map,0,sizeof(map)); 
for(i=0; i<m; i++) 
\{ 
scanf("%d%d",&u,&v); 
if(!map\[u\]\[v\]) 
\{ 
in\[v\]++; 
map\[u\]\[v\]=1; 
\} 
\} 
tpsort(); 
\} 
return 0; 
\}