确定比赛名次
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 8569 Accepted Submission(s): 3314
其他说明:符合条件的排名可能不是唯一的,此时要求输出时编号小的队伍在前;输入数据保证是正确的,即输入数据确保一定能有一个符合要求的排名。
题意:
给N个队伍,根据M个信息对这N个队伍排序。
思路:
注意两个地方:
1.输入有若干组,所以需要用while(scanf("%d%d",&n,&m)!=EOF)来输入数据;
2.输入的排名信息都有是有效的排名信息,但是有重边的情况(重边就是排名信息有两次或两次以上是一样的),所以在判断入度+1的时候要先判断map[A][B]是否=1,如果已经等于1,说明曾经已经输入过这个 排名信息;
3.因为给出的都是有效的排名信息(Output有说明”输入数据保证是正确的,即输入数据确保一定能有一个符合要求的排名“),所以不需要考虑有环的情况,有环则不可能”给出一个符合要求的排名“,但是有可能给的信息不完全,比如说1排在3的前面,2也排在3的前面,那么1和2的排名顺序是不确定的,Output有要求说明“要求输出时编号小的队伍在前”,则这时候的情况应该是1,2,3.
4.在输出格式方面也有要求的地方,“输出时队伍号之间有空格,最后一名后面没有空格”,在输出的时候应该注意一下。
AC:
邻接矩阵写法:
#include<stdio.h> #include<string.h> int main() { int n,m; int i,j,k; int a,b; int map[505][505],indegree[505]; while(scanf("%d%d",&n,&m)!=EOF) { memset(map,0,sizeof(map)); memset(indegree,0,sizeof(indegree)); for(i=0;i<m;i++) { scanf("%d%d",&a,&b); //增加一步判断map[a][b]是否等于0 //等于0说明之前的判断信息与之重复,等于1说明之前的判断信息与之重复 if(!map[a][b]) { indegree[b]++; map[a][b]=1; } } //输入完成后,排列的信息已经存储在map矩阵和indegree入度数组中 //以下为拓扑排序的步骤 for(i=1;i<=n;i++) //i循环排序 { for(j=1;j<=n;j++) //j循环是为了遍历indegree入度数组,找入度为0的项 //一定会有入度为0的情况的,因为题目要求不可能给出有环的情况 { if(!indegree[j]) { if(i==1) printf("%d",j); else printf(" %d",j); //找到后直接输出,不需要再存到另外一个数组那里 //这里的输出要注意格式 indegree[j]=-1; //删除这个节点 for(k=1;k<=n;k++) //k的循环是为了找与之邻接的节点 if(map[j][k]) indegree[k]--; //同时删除与之邻接的结点的入度 break; //为什么要break? //是因为保证每次找到的都是第一个,这就符合了“输出时编号小的排序在前”的要求 } } } printf("\n"); } return 0; }
总结:
理解清楚题目的话,就不会想到要判断环的情况了,可能是做了之前那道更难的拓扑排序题目的关系,所以会不知不觉想到有环,或者给的判断信息不全的情况,所以学习一个新的知识后,做题的时候最好还是由浅入深。还有一个点需要注意:
for(i=0;i<m;i++) { scanf("%d%d",&a,&b); //这里输入了两个个数之后 if(!map[a][b]) { indegree[b]++; map[a][b]=1; } //这里就直接以下标为a和b的数来赋值,这时候应该清楚 //下标应该是从1开始的,而不是0,所以下面的循环遍历排序的时候,应该从1开始 }
一开始测试的时候输出0,1,2,4,还在纳闷为什么会这样输出,后来就发现了是这个问题了,所以还是得注意这些细节的问题。
相关推荐
该PPT详细的讲了拓扑序,适合初学者看,可有点简单,所以你只用1积分就可以下载了。
算法-确定比赛名次(HDU-1285).rar
甲猜的名次顺序为A、B、C、D、E,结果没有猜中任何一个学生的名次,也没有猜中任何一对相邻名次(所谓一对相邻名次,是指其中一对选手在名次上邻接。例如1与2,或者2与3等)。乙猜的名次顺序为D、A、E、C、B,...
甲猜的名次顺序为A、B、C、D、E,结果没有猜中任何一个学生的名次,也没有猜中任何一对相邻名次(所谓一对相邻名次,是指其中一对选手在名次上邻接。例如1与2,或者2与3等)。乙猜的名次顺序为D、A、E、C、B,...
兔子小白参加了兔界里的数学比赛,成绩公布后,小白很想知道自己的成绩到底排第几,动物界排名有个规定,如果有相同的分数,就并列名次,而且下一个分数不递减名次,比如:有三个分数100、100、90,90分就认为是第2...
循环比赛的名次 图与网络 适用于数学建模培训和人工智能学习
实现学生信息中的成绩输入、文件输出、名次排序等,非常的强大
某学校有8名同学参加100米短跑比赛, 每个运动员号和成绩看图(略), 请按照比赛成绩排名并输出, 要求每一行输出名次、运动员号、姓名和比赛成绩四项数据
表格模板-成绩排序名次表.xlsx
5位运动员参加了10米台跳水比赛,有人让他们预测比赛结果Matlab程序
为方便一些歌咏、舞蹈或者技能等节目汇演比赛的...只需录入每个评委的实际评分,便可以自动实现最高分、最低分统计、实现去除高低分后根据实际参与评分的评委个数计算平均分,最后按照比赛名次进行参赛单位的自动排列。
汇编语言综合性实验报告-显示学生名次(含代码).docx汇编语言综合性实验报告-显示学生名次(含代码).docx汇编语言综合性实验报告-显示学生名次(含代码).docx汇编语言综合性实验报告-显示学生名次(含代码).docx汇编语言...
冒泡排序算法的实现,用C语言实现,并含有测试程序。程序已经测试通过。 /* * --冒泡排序-- * 依次比较相邻的两个数,将大数放在前面,小数放在后面。 * 即首先比较第1个和第2个数,将大数放前,小数放后。 ...
然后根据GRADE中的学生成绩,把学生名次填入50字节的RANK数组中,其中RANK+N的内容是学号为N+1学生的名次。再按学号把学生顺序和学生名次显示出来。 实验要求:1.必须画流程图。2.本程序要求要有多重循环和子程序,...
微机原理课程设计报告_学生成绩排序名次.pdf
各项目名次取法有如下几种: 取前5名:第一名得分7分,第二名得分5,第三名得分3,第四名得分2,第五名得分1;取前3名:第一名得分5, 二名得分3,第三名得分2; 功能要求: (1)系统以菜单方式工作 (2)由程序...
各省市旅游局网站排列名次名次.pdf
编制一程序,要求接收从键盘输入的一个班的学生成绩,并...然后根据GRADE中的学生成绩,把学生名次填入50字节的RANK数组中,其中RANK+N的内容是学号为N+1学生的名次。再按学号顺序和学生名次顺序把学生成绩显示出来。
各项目名次取法有如下几种: 取前5名:第一名得分7分,第二名得分5,第三名得分3,第四名得分2,第五名得分1; 取前3名:第一名得分5,第二名得分3,第三名得分2; 功能要求: (1)系统以菜单方式工作 (2)由程序...
输入1是数据录入并输出(包括姓名、学号、成绩); 输入2是排序后的数据输出(包括姓名、学号、成绩、名次); 输入3是可以按学号查找某学生,并输出其成绩,选择修改或不改成绩。