HDOJ 1285試合順位決定(トポロジーソート、4つの実現方法)
6788 ワード
試合の順位を決める
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 17294 Accepted Submission(s): 6888
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行データでは、行ごとに2つの整数P 1があり、P 2はP 1チームがP 2チームに勝ったことを示す.
Output
要件に合致するランキングを与えます.出力時にキュー番号の間にスペースがあり、最後の名前の後ろにスペースがありません.その他の説明:条件に合致する順位は唯一ではない可能性があります.この場合、出力時の番号の小さいチームが上位にあることが要求されます.入力データは正しいことを保証します.すなわち、入力データは必ず要求に合致するランキングを確保します.
Sample Input
Sample Output
1、素朴なやり方、コードは以下の通りです.
2、隣接テーブルを実現し、メモリを減らす.隣接する表はまだ分かりませんが、コードは以下の通りです.
3,STLキュー実装,コードは以下の通りである.
4,優先キュー実装,コードは以下の通りである.
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 17294 Accepted Submission(s): 6888
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行データでは、行ごとに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
1、素朴なやり方、コードは以下の通りです.
<span style="font-size:12px;">#include<cstdio>
#include<cstring>
int ans[510][510];//
int n,indegree[510];//
int queue[510];//
void tuopu()
{
int i,j,top,k=0;
for(j=0;j<n;++j)
{
for(i=1;i<=n;++i)
{
if(indegree[i]==0)//
{
top=i;
break;
}
}
queue[k++]=top;//
indegree[top]=-1;// -1，
for(i=1;i<=n;++i)
{
if(ans[top][i])//
indegree[i]--;
}
}
for(i=0;i<k-1;++i)
printf("%d ",queue[i]);
printf("%d
",queue[n-1]);
}
int main()
{
int i,a,b,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(indegree,0,sizeof(indegree));
memset(ans,0,sizeof(ans));
for(i=0;i<m;++i)
{
scanf("%d%d",&a,&b);
if(ans[a][b]==0)
{
ans[a][b]=1;//
indegree[b]++;//
}
}
tuopu();
}
return 0;
}</span>2、隣接テーブルを実現し、メモリを減らす.隣接する表はまだ分かりませんが、コードは以下の通りです.
<span style="font-size:12px;">#include<cstdio>
#include<cstring>
int n,indegree[510];
int queue[510],head[510];
struct node
{
int to,next;
}ans[510];
void tuopu()
{
int i,j,top,k=0,cnt;
for(j=0;j<n;++j)
{
for(i=1;i<=n;++i)
{
if(indegree[i]==0)
{
top=i;
break;
}
}
queue[k++]=top;
indegree[top]=-1;
for(cnt=head[top];cnt!=-1;cnt=ans[cnt].next)// ， ，
indegree[ans[cnt].to]--;
}
for(i=0;i<n-1;++i)
printf("%d ",queue[i]);
printf("%d
",queue[n-1]);
}
int main()
{
int i,a,b,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(indegree,0,sizeof(indegree));
memset(head,-1,sizeof(head));
for(i=0;i<m;++i)
{
scanf("%d%d",&a,&b);
ans[i].to=b;//
ans[i].next=head[a];
head[a]=i;
indegree[b]++;
}
tuopu();
}
return 0;
}</span>3,STLキュー実装,コードは以下の通りである.
<span style="font-size:12px;">#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int ans[510][510];
int n,indegree[510];
void tuopu()
{
int i,j,t,top;
queue<int>q;
for(i=1;i<=n;++i)
{
if(indegree[i]==0)
{
q.push(i);
break;
}
}
int sign=1;
while(!q.empty())
{
top=q.front();
q.pop();
indegree[top]=-1;
if(sign)
{
printf("%d",top);
sign=0;
}
else
printf(" %d",top);
for(i=1;i<=n;++i)// ，
{
if(ans[top][i]==1)
indegree[i]--;
}
for(i=1;i<=n;++i)
{
if(indegree[i]==0)
{
q.push(i);
break;
}
}
}
printf("
");
}
int main()
{
int i,m,a,b;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(indegree,0,sizeof(indegree));
memset(ans,0,sizeof(ans));
for(i=0;i<m;++i)
{
scanf("%d%d",&a,&b);
if(ans[a][b]==0)
{
ans[a][b]=1;
indegree[b]++;
}
}
tuopu();
}
return 0;
}</span>4,優先キュー実装,コードは以下の通りである.
<span style="font-size:12px;">#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int ans[510][510];
int n,indegree[510];
void tuopu()
{
int i,j,t,top;
priority_queue<int,vector<int>,greater<int> >q;//
for(i=1;i<=n;++i)
{
if(indegree[i]==0)
q.push(i);
}
int sign=1;
while(!q.empty())
{
top=q.top();
q.pop();
indegree[top]=-1;
if(sign)
{
printf("%d",top);
sign=0;
}
else
printf(" %d",top);
for(i=1;i<=n;++i)
{
if(ans[top][i])
{
indegree[i]--;
if(indegree[i]==0)
q.push(i);
}
}
}
printf("
");
}
int main()
{
int i,m,a,b;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(indegree,0,sizeof(indegree));
memset(ans,0,sizeof(ans));
for(i=0;i<m;++i)
{
scanf("%d%d",&a,&b);
if(ans[a][b]==0)
{
ans[a][b]=1;
indegree[b]++;
}
}
tuopu();
}
return 0;
}</span>