题解 [ABC139E] League
Lskkkno1
·
·
题解
题意简述
且每个人每天只可以比一场比赛，问最少比赛的天数为多少，无解输出 -1。
### 正解
发现一个人假如可以和另外一个打比赛时，和他打比赛肯定是最优的。
因为另外那个人此时肯定也只可以和他打比赛，对除了这两人之外的其他人没有影响。
每一场比赛都可以用一个二元组表示 $(x, y)$ 成一个节点，节点向节点连边表示限制。
比如说第一个人要先后和第二个人和第三个人打比赛， 那么 $(1, 2) \to (1,3)$。
这样的话只有入度为 $0$ 的点（比赛）才可以进行，用 topo 排序做一下。
给出结论：有环的话肯定无解，没环的话答案就是最长链。
前一个很好证明，关键是后面一个怎么证明。
其实也挺好证，因为当前入度为 $0$ 的节点（比赛）肯定都可以在同一天进行完。
具体一点 ：$(1,2)$ 和 $(1,3)$ 肯定不会同时可以进行比赛（同时入度为 $0$）。
**Code :**
```cpp
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <queue>
#define N 1003
using namespace std;
struct edge{
int to, nxt;
}e[N * N * 3];
int n, cnt;
int ins[N * N], mp[N][N], fir[N * N], t[N * N];
queue < int > Q;
int id(int ,int);
void add(int ,int);
int main(){
scanf("%d", &n); int ans = 0;
for(int i = 1; i <= n; ++i)
for(int j = 1; j < n; ++j)
scanf("%d", mp[i] + j);
for(int i = 1; i <= n; ++i)
for(int j = 2; j < n; ++j)
add(id(i, mp[i][j - 1]), id(i, mp[i][j]));
for(int i = 1; i <= n * n; ++i){
if(!ins[i]) Q.push(i);
t[i] = 1;
}
while(!Q.empty()){
int u = Q.front(); Q.pop(); ans = max(ans, t[u]);
for(int i = fir[u]; i; i = e[i].nxt){
int v = e[i].to;
--ins[v];
if(!ins[v])
Q.push(v), t[v] = t[u] + 1;
}
}
for(int i = 1; i <= n * n; ++i)
if(ins[i]) ans = -1;
cout << ans << endl;
return 0;
}
int id(int x,int y){
if(x > y) swap(x, y);
return (x - 1) * n + y;
}
void add(int u,int v){
e[++cnt] = (edge){v, fir[u]}; fir[u] = cnt; ++ins[v];
return ;
}
```