rank.cpp

两道程序设计竞赛的题目

#include <string.h>
#include <stdio.h>
#include <math.h>
#define MAXN 110 //大学数目的最大值
#define MAXM 110 //专业数目的最大值
long N,M;//N表示大学数目，M表示专业数目
long rank[MAXN][MAXM];//rank[i][j]表示大学i在专业j上的排名
bool b[MAXN][MAXN];//b[i][j]表示大学i优于大学j
long outd[MAXN];//outd[i]表示有向图的顶点i的出度
/* 读取测试数据，并构造对应的有向无环图*/
void  input()
{
	long i,j,k,x;
	scanf("%ld%ld",&N,&M);
	for(i=0;i<M;i++){
		for(j=0;j<N;j++)
		{
			scanf("%ld",&x);
			x--;
			rank[x][i] = j; //读入数据
		}	    
}
	memset(b,0,sizeof(b));
	memset(outd,0,sizeof(outd));
	for(i=0;i<N;i++)
		for(j=0;j<N;j++)
	{
		//判断大学i是否优于大学j
		for(k=0;k<M;k++)
			if(rank[i][k] >= rank[j][k])
				break;
         if(k>=M) //标记大学i优于大学j,并更新顶点i的出度
		 {
			b[i][j] =1;
			outd[i]++;
		 }

	}
}
//求有向无环图的最长路
long solve()
{
	long v[MAXN],flag = 1,anwser =0,i,j,t;//V[i]表示到顶点i的最长路长度
	memset(v,0xff,sizeof(v));
	while(flag)
	{
		flag =0;
		for(i=0;i<N;i++)
			if(!outd[i] && v[i]<0){//扫描每个出度为0且未被标记的点
				flag = 1;
				for(t=0,j=0;j<N;j++)
					if(b[i][j]&&v[j]>t) t=v[j];
					v[i] = t+1;
					if(v[i]>anwser) anwser = v[i]; //更新顶点i的最长路长度
                   //删除边（i,j),并更新点j的出度
					for(j=0;j<N;j++) 
						if(b[j][i])
							outd[j]--;
			}
	}
	return anwser;
}
int main()
{
	freopen("c:/rank.in","r",stdin);
	freopen("c:/rank.out","w",stdout);
	long c;
	scanf("%ld",&c);
	while(c--)
	{
		input();
		printf("%ld\n",solve());
	}
	return 0;
}