hdoj 1285 确定比赛名次【拓扑】

秒速五厘米 2022-08-04 13:44 105阅读 0赞

# 确定比赛名次 #

**Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)  
Total Submission(s): 17739    Accepted Submission(s): 7097**

Sample Input

4 3
    1 2
    2 3
    4 3

Sample Output

1 2 4 3

题目大意：略

思路：先统计哪些队伍输了比赛，输了几次（用一个一维数组即可表示，数组序号表示队伍号，每输一次，数组对应的元素加一，当一只队不能输给同一支队伍两次），然后查找那些没有输过的（即当前最屌的队伍），让他们入队，让后再把那些数个这只对的失败次数减一；接着在查找失败次数为零的队伍，让他们入队......（重复前面的步骤，知道把所有队伍都标记为已记录）。

已Accept代码（c++提交）【用到队列，其实用数组就可以存】

#include<cstdio>
    #include<queue>
    #include<cstring>
    using namespace std;
    int p[501][501];
    int ind[501];					//存放某队输的次数 
    int m,n;
    
    void topo(){
    	queue<int>q;				//用来放排名 
    	while(!q.empty()) q.pop();	//清空队列 
    	int e=0;
    	int i,j;
    	while(e!=n){
    		for(i=0;ind[i]!=0;i++);	//找出当前入度为零的人 （即东方不败 （^.^）） 
    		ind[i]=-1;				//标记为 -1 ，表示已访问 (即下文中说的去掉i)
    		for(j=0;j<n;j++){
    			if(p[i][j]==1)		//i为胜者，j为败者，i已去掉， 
    				ind[j]--;		//故j的失败次数减一
    		}
    		q.push(i+1);			//当前排名最靠前的入队 
    		e++;
    	}
    	printf("%d",q.front());
    	q.pop();
    	while(!q.empty()){
    		printf(" %d",q.front());
    		q.pop();
    	}
    	printf("\n");
    }
    
    int main(){
    	while(scanf("%d%d",&n,&m)!=EOF){
    		int a,b;
    		memset(ind,0,sizeof(ind));
    		memset(p,0,sizeof(p));
    		for(int i=0;i<m;i++){
    			scanf("%d%d",&a,&b);
    			if(!p[a-1][b-1]){		//判断 a 是否已经赢过 b
    				p[a-1][b-1]=1;		//未赢，则标为 1（即标记为已经赢过 ） 
    				ind[b-1]++;			// b 入度加一 (即输的次数加一)
    			}
    		}
    		topo();
    	}
    	return 0;
    }

下面的代码为用数组来代替上面的队列，注释同步；（c提交）

#include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    int p[501][501];
    int indegree[501],x[501];
    int n,m;
    
    void topo(){
    	int cnt=0;
        int k=0;
        int i,j;
        while(cnt!=n){
            for(i=0;indegree[i]!=0;i++);
            indegree[i]=-1;
            for(j=0;j<n;j++){
                if(p[i][j]==1)
                    indegree[j]--;
            }
            x[k++]=i+1;
            cnt++;
        }
        printf("%d",x[0]);
        for(i=1;i<n;i++)
        printf(" %d",x[i]);
        printf("\n");
    }
    
    int main(){
        int i,j,a,b;
        while(scanf("%d%d",&n,&m)!=EOF){
            memset(p,0,sizeof(p));
            memset(indegree,0,sizeof(indegree));
            for(i=0;i<m;i++){
                scanf("%d%d",&a,&b);
                if(!p[a-1][b-1]){
                    p[a-1][b-1]=1;
                    indegree[b-1]++;
                }
            }
            topo();
        }
        return 0;
    }