且构网

分享程序员开发的那些事...
且构网 - 分享程序员编程开发的那些事

hdu 1285 确定比赛名次(很典型的拓扑排序)

更新时间:2022-08-20 23:04:16

题目连接 : http://acm.hdu.edu.cn/showproblem.php?pid=1285

拓扑排序,很明显的一道拓扑排序的问题,用一个二维数组存储两个数字之间的关系,如果某个数大于另一个数,那么它们之间的关系为1,否则为0.

如果存在关系为1的两个数据,那么行表示比列大。列的下标入度自增1.然后使用拓扑排序思想依次取出每个节点。

此题可参考类似题目 http://www.cnblogs.com/newpanderking/archive/2012/10/16/2726757.html 这也是一道经典的拓扑排序

hdu 1285 确定比赛名次(很典型的拓扑排序)
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 510
using namespace std;
/*
拓扑排序解法
*/

int rela[maxn][maxn];
int in_degree[maxn],ans[maxn];
int n,m,x,y;

void top_order()
{
    //预处理
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    if(rela[i][j])in_degree[j]++;

    for(int i=1;i<=n;i++)
    {
        int k=1;
        while(in_degree[k]!=0)k++;
        ans[i]=k;
        in_degree[k]--;//更新为-1,后边检测时不受影响
        for(int j=1;j<=n;j++)
        if(rela[k][j])
        in_degree[j]--;//相关联的入度减1

    }

}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(in_degree,0,sizeof(in_degree));
        memset(ans,0,sizeof(ans));
        memset(rela,0,sizeof(rela));
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&x,&y);
            rela[x][y]=1;
        }
        top_order();
        for(int i=1;i<n;i++)
        printf("%d ",ans[i]);
        printf("%d\n",ans[n]);
    }
    return 0;
}
hdu 1285 确定比赛名次(很典型的拓扑排序)






本文转自NewPanderKing51CTO博客,原文链接:http://www.cnblogs.com/newpanderking/archive/2012/11/08/2759608.html ,如需转载请自行联系原作者