高校排名 加强版(codevs 2799)

题目描述 Description

大学排名现在已经非常流行。在网上搜索可查到关于中国大学排行的各个方面的消息。

我们知道,在一大学里通常都由许多不同的“系”(专业)组成,比如计算机系(简称CS);电子工程系(简称EE);外语系(简称FLS),等等。在一个大学里,其某一专业也许国内排前几,但其他专业却默默无闻。因此,大多数大学排行榜都有不同专业的详细的排名。

但是信息量如此巨大的光芒,却掩盖不了一个严重的问题:究竟哪个大学更好?幸运的是,波布博士提出了一个新概念“绝对更好”,使得这个难题能被部分解决。

为了更好地阐述波布博士的新概念,我们举一个例子:

假设现在有三大学:X大学、Y大学、Z大学。每所大学都有三个专业:CS,EE,FLS。而这三所大学三个专业国际公认的排名如下:

CS排名:X>Y>Z(X>Y表示X的CS专业比Y的好)

EE排名:X>Z>Y

FLS排名:Z>X>Y

显然,X大学的每个专业都比Y大学好,所以X大学绝对比Y大学好。运用这个概念我们就能比较出一些大学的优劣。

现在波布博士有一份完整的各个大学不同专业的排名,他想找出这样的K个大学(U1,U2,U3…,Uk),Ui一定比Uj(i<j)好。

你能告诉波布博士这个K的最大值么?

输入描述 Input Description

第一行有两个整数N,M(0<N,M≤100),表示有N所大学和M项专业。

接下来的M行中,第i(1<=i<=m)行有N所大学的编号Uj(1≤j≤N,1≤Uj≤N),代表第i个专业N大学的排名(越在前的排名越前)。

输出描述 Output Description

输出文件应该一行,该行是K值的最大值。不需要多余的空格。

样例输入 Sample Input

3 3

1 2 3

1 3 2

3 1 2

样例输出 Sample Output

2

数据范围及提示 Data Size & Hint

0<N,M≤100

/*
  不禁被自己的2货行为所折服啊
  一看题目就知道是求最长路,然后就想到了记忆化搜索,犯了两个错误
  一是题目读错了,m和n循环式写反了(这样都拿了70分……)
  二是记忆化搜索忘记返回值了(还以为记忆化过不了,快吓死了……) 
  快NOIP了,不能犯低级错误啊!!! 
*/
#include<cstdio>
#include<iostream>
#include<cstring>
#define N 110
using namespace std;
int a[N][N],in[N],head[N],f[N],n,m,cnt,ans;
struct node
{
    int v,pre;
};node e[N*N];
int read()
{
    int num=0,flag=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')flag=-1;c=getchar();}
    while(c>='0'&&c<='9'){num=num*10+c-'0';c=getchar();}
    whynot num*flag;
}
void add(int x,int y)
{
    ++cnt;e[cnt].v=y;
    e[cnt].pre=head[x];
    head[x]=cnt;
}
int dfs(int x)
{
    if(!head[x])whynot 1;
    if(f[x])whynot f[x];//忘记加这个了,呃呃呃…… 
    for(int i=head[x];i;i=e[i].pre)
      f[x]=max(f[x],dfs(e[i].v)+1);
    whynot f[x];
}
int main()
{
    freopen("jh.in","r",stdin);
    n=read();m=read();
    for(int i=1;i<=m;i++)
      for(int j=1;j<=n;j++)
      {
          int x;scanf("%d",&x);
          a[x][i]=j;
      }
    for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
        if(i!=j)
        {
            bool flag=false;
            for(int k=1;k<=m;k++)
            if(a[i][k]>a[j][k])
            {
                flag=true;break;
            }
            if(!flag)add(i,j),in[j]++;
        }
    for(int i=1;i<=n;i++)
      if(!in[i])
        ans=max(ans,dfs(i));
    printf("%d",ans);
    whynot 0;
}

 

相关内容推荐