HDOJ-1285--試合の順位を確定する
2096 ワード
試合の順位を決める
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 17172 Accepted Submission(s): 6820
Problem Description
Nチーム(1<=N<=500)があり、番号は1、2、3、..
.
,Nは試合を行い,試合終了後,審判委員会は全参加チームを行き順に順位付けする.しかし、現在、審判委員会は各チームの試合成績を直接獲得することができず、試合の結果だけを知っている.すなわちP 1がP 2に勝ち、P 1を用いる.P 2で表します.順位はP 1がP 2より前.
今、ランキングを確定するプログラムを作ってください.
Input
入力にはいくつかのグループがあり、各グループの第1の動作の2つの数N(1<=N<=500)、M;このうちNは行列の個数を示し,MはM行の入力データが続くことを示す.次のM行データでは、1行につき2つの整数P 1がある.P 2はP 1チームがP 2チームに勝ったことを示す.
Output
要件に合致するランキングを与えます.
出力時にキュー番号の間にスペースがあり、最後の名前の後ろにスペースがありません.その他の説明:条件に合致するランキングは一意ではない場合がありますが、出力時に番号の小さいチームが上位にあることが要求されます.入力データは正しいことを保証します.すなわち、入力データは必ず要求に合致するランキングを確保します.
Sample Input
転載先:https://www.cnblogs.com/yxysuanfa/p/7132206.html
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 17172 Accepted Submission(s): 6820
Problem Description
Nチーム(1<=N<=500)があり、番号は1、2、3、..
.
,Nは試合を行い,試合終了後,審判委員会は全参加チームを行き順に順位付けする.しかし、現在、審判委員会は各チームの試合成績を直接獲得することができず、試合の結果だけを知っている.すなわちP 1がP 2に勝ち、P 1を用いる.P 2で表します.順位はP 1がP 2より前.
今、ランキングを確定するプログラムを作ってください.
Input
入力にはいくつかのグループがあり、各グループの第1の動作の2つの数N(1<=N<=500)、M;このうちNは行列の個数を示し,MはM行の入力データが続くことを示す.次のM行データでは、1行につき2つの整数P 1がある.P 2はP 1チームがP 2チームに勝ったことを示す.
Output
要件に合致するランキングを与えます.
出力時にキュー番号の間にスペースがあり、最後の名前の後ろにスペースがありません.その他の説明:条件に合致するランキングは一意ではない場合がありますが、出力時に番号の小さいチームが上位にあることが要求されます.入力データは正しいことを保証します.すなわち、入力データは必ず要求に合致するランキングを確保します.
Sample Input
4 3 1 2 2 3 4 3
Sample Output
1 2 4 3
思路：应该说是拓扑排序中的模板题。我也是今天才学，详细模板见代码。
ac代码：
#include
#include
#include
using namespace std;
int map[510][510];//
int indegree[510];//
int queue[510];//
void topo(int n)
{
int i,j,m,t=0;
for(j=0;j 転載先:https://www.cnblogs.com/yxysuanfa/p/7132206.html