首页 > ACM题库 > HDU-杭电 > HDU 1285 确定比赛名次-排序-[解题报告] C++
2013
12-04

HDU 1285 确定比赛名次-排序-[解题报告] C++

确定比赛名次

问题描述 :

有N个比赛队(1<=N<=500),编号依次为1,2,3,。。。。,N进行比赛,比赛结束后,裁判委员会要将所有参赛队伍从前往后依次排名,但现在裁判委员会不能直接获得每个队的比赛成绩,只知道每场比赛的结果,即P1赢P2,用P1,P2表示,排名时P1在P2之前。现在请你编程序确定排名。

输入:

输入有若干组,每组中的第一行为二个数N(1<=N<=500),M;其中N表示队伍的个数,M表示接着有M行的输入数据。接下来的M行数据中,每行也有两个整数P1,P2表示即P1队赢了P2队。

输出:

给出一个符合要求的排名。输出时队伍号之间有空格,最后一名后面没有空格。

其他说明:符合条件的排名可能不是唯一的,此时要求输出时编号小的队伍在前;输入数据保证是正确的,即输入数据确保一定能有一个符合要求的排名。

样例输入:

4 3
1 2
2 3
4 3

样例输出:

1 2 4 3

http://acm.hdu.edu.cn/showproblem.php?pid=1285

 

最简单的拓扑排序

 

拓扑排序方法如下:   (1)从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它.   (2)从网中删去该顶点,并且删去从该顶点发出的全部有向边.   (3)重复上述两步,直到剩余的网中不再存在没有前驱的顶点或者所有的点都排序完毕为止.

#include<stdio.h>
#include<string.h>
#define N 505
int map[N][N],index[N],used[N],n,m;
//map表示邻接矩阵,index记录入度,used记录是否排序
void toposort()
{
	int i,j,topo=0;
	while(topo<n){
		for(i=1;i<=n;i++){
			if(index[i]==0&&used[i]==0){//i从小到大,号码小的优先
				used[i]=1;break;//删除入度为0的点
			}
		}
		if(i==n+1)return;//如果没有入度为一的点则结束
		if(topo)
			printf(" ");
		printf("%d",i);
		topo++;
		for(j=1;j<=n;j++){//将所有以 i 为起点的边删除
			if(map[i][j]==1){
				map[i][j]=0;
				index[j]--;
			}
		}
	}
}
int main()
{
	int i,a,b;
	while(scanf("%d%d",&n,&m)!=EOF){
		memset(map,0,sizeof(map));
		memset(index,0,sizeof(index));
		memset(used,0,sizeof(used));
		for(i=1;i<=m;i++){
			scanf("%d%d",&a,&b);
			if(map[a][b]==0){//考虑重边的情况
				map[a][b]=1;
				index[b]++;
			}
		}
		toposort();
		printf("\n");
	}
	return 0;
}


  1. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  2. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的

  3. /*
    * =====================================================================================
    *
    * Filename: 1366.cc
    *
    * Description:
    *
    * Version: 1.0
    * Created: 2014年01月06日 14时52分14秒
    * Revision: none
    * Compiler: gcc
    *
    * Author: Wenxian Ni (Hello World~), [email protected]
    * Organization: AMS/ICT
    *
    * =====================================================================================
    */

    #include
    #include

    using namespace std;

    int main()
    {
    stack st;
    int n,i,j;
    int test;
    int a[100001];
    int b[100001];
    while(cin>>n)
    {
    for(i=1;i>a[i];
    for(i=1;i>b[i];
    //st.clear();
    while(!st.empty())
    st.pop();
    i = 1;
    j = 1;

    while(in)
    break;
    }
    while(!st.empty()&&st.top()==b[j])
    {
    st.pop();
    j++;
    }
    }
    if(st.empty())
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
    }
    return 0;
    }

  4. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。