有n(1000)个人, 每个人都要和其他n−1个人进行比赛, 每个人都规定了他参加的n−1场比赛的顺序, 问是否有一种比赛顺序能满足所有人心意. 此外, 每天可以安排多场比赛,但每天一个人只能参加一场比赛. 如果不能满足所有人的心意输出−1, 如果能够满足所有人心意, 那么输出最少需要比赛多少天.
设[A,B]代表A和B两个人进行的那场比赛.
可以把[A,B]当作一个点, 那么题目给出的关系矩阵就会构成一个有关每场[比赛]的无向图. 图上的边[A,B]→[A,C]代表先进行[A,B]才能进行[A,C].
只有当这个图是DAG的话, 才能满足所有人的心意. 在此基础上, DAG上的最长路就是花费的最长时间, 在最长路之外的点都能在走最长路的过程中走完.
判断DAG: O(N+V). DAG上最长路: (简单dp)O(N+V)
const int M = 1123456;
int n, fa[M],inDg[M],cnt = 0;
vector<int> to[M];
set<int> points;
void dfs(int now) {
cnt++;
for (auto son:to[now]) {
inDg[son]--;
if (inDg[son] == 0) {
dfs(son);
}
}
}
int dp[M];
int dfs2(int now) {
if (dp[now] != -1)
return dp[now];
int tmp = 0;
for (auto son:to[now]) {
checkMax(tmp, dfs2(son) + 1);
}
return dp[now] = tmp;
}
void init() {
Mem(dp, -1);
n = read();
for (int i = 1; i <= n; ++i) {
int bf = 0;
points.insert(0);
for (int j = 1; j < n; ++j) {
int tmp1 = read();
int tmp2 = i;
if (tmp1 > tmp2)swap(tmp1, tmp2);
int tmp = tmp1 * 1000+ tmp2;
// 用 小人编号*1000+大人编号 唯一确定一场比赛
points.insert(tmp);
fa[tmp] = bf;
to[bf].emplace_back(tmp);
inDg[tmp]++;
bf = tmp;
}
}
dfs(0);
if (cnt < points.size()) {
puts("-1");
return;
}
write(dfs2(0)), enter;
// 实际上求的是经过了多少条边, 但我们的根节点是0, 所以就不用+1了
}