2. 高校排名
题目ID：11053必做题100分
最新提交：
Wrong Answer
80 分
历史最高：
Wrong Answer
80 分
时间限制: 1000ms
空间限制: 524288kB
题目描述
1s, 512MB
【问题描述】
现有3个大学：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大学好。
现在有N个大学，M个专业，给出各个大学各个专业的排名情况，我们希望找出一个含若干个大学的有序序列，序列除最后一个大学外，任意一个大学都比他后面的大学要绝对的好。（参见样例说明）
比如我们找到这样一个序列，U2>U5>U7>U4,该序列元素个数K=4。
现要求K的最大值是多少？
【输入文件】
第一行有两个整数N和M
接下来M行中，第i（1<=i<=M）行有N个大学的编号，代表第i个专业的排名，排名越靠前的学校编号，表示该学校的该专业越好。
【输出文件】
一个整数K。
【样例输入1】
4 3
1 2 3 4
1 3 2 4
3 1 2 4
【样例输出1】
3
【样例输入2】
5 3
4 2 1 3 5
2 4 1 5 3
1 4 3 2 5
【样例输出2】
2
【样例输入3】
7 4
7 4 5 6 2 1 3
4 6 1 7 2 3 5
4 7 5 6 2 3 1
1 2 3 4 5 6 7
【样例输出3】
2
【样例输入4】
9 5
1 2 3 4 5 6 7 8 9
2 6 3 5 1 9 4 8 7
4 2 7 3 8 9 6 1 5
1 2 3 5 4 7 9 6 8
4 2 3 1 7 5 8 6 9
【样例输出4】
3
【样例说明】
满足条件的序列有U1>U2， U1>U4 ，U2>U4, U3>U4， U1>U2>U4，最大值为3
【数据范围】
对于60%的数据，1<=N<=20
对于100%的数据，1<=N,M<=100
本帅哥的代码
#include <bits/stdc++.h>
#define int long long //用>>>代表绝对好
using namespace std; //u=univercity ans[i]:比如u1>>>u2>>>u3,ans[1]=3,ans[2]=2,ans[3]=1
int n, m, jl[105][105] = {0}/*jl[i][j]=666表示i不比j绝对好,jl[i][j]=1表示i比j绝对好*/, u[105][105], ans[105], pre[105][105] = {0};
/*pre[i][j]表示所有比学校i绝对好,pre[i][j]是第j所学校(j仅仅是计数)*/
signed main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int ko, last;
for (int j = 1; j <= n; j++) {
last = ko;
cin >> ko;
u[i][ko] = j;
if (j > 1) {
jl[ko][last] = 666;
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (jl[i][j] == 666) {
continue;
}
if (i == j) {
jl[i][j] = 666;
continue;
}
for (int k = 1; k <= m; k++) {
if (u[k][i] < u[k][j]) {
jl[j][i] = 666;
} else {
jl[i][j] = 666;
}
}
if (jl[i][j] != 666) {
jl[i][j] = 1;
}
if (jl[j][i] != 666) {
jl[j][i] = 1;
}
}
}
/*这3个for循环意思大概是：若jl[i][j] = 1, jl[j][k] = 1, 将jl[i][k] = 1改为jl[i][k] = 114514,后期改为666;*/
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (jl[i][j] == 1 || jl[i][j] == 114514) {
for (int k = 1; k <= n; k++) {
if (jl[j][k] == 1 || jl[j][k] == 114514) {
jl[i][k] = 114514;
}
}
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (jl[i][j] == 114514) {/*将114514改为666*/
jl[i][j] = 666;
}
if (jl[i][j] == 1) {
int k;
for (k = 1; pre[j][k] != 0; k++) {
continue;
}
pre[j][k] = i;
}
}
}
for (int i = 1; i <= n; i++) {
bool flag = false;
for (int j = 1; j <= n; j++) {
if (jl[i][j] == 1) {
flag = true;
}
}
if (!flag) {
ans[i] = 1;
}
}
for (int i = 1; i <= n; i++) {
if (ans[i] == 1) {
int j = i, l, cnt = 1;
while (pre[j][cnt] != 0) {
l = j;
j = pre[j][cnt];
ans[j] = ans[l] + 1;
cnt++;
}
}
}
int zhongyu = -1;
for (int i = 1; i <= n; i++) {
zhongyu = max(zhongyu, ans[i]);
}
cout << zhongyu;
return 0;
}