[ABC139E] League 题解

题目链接：[ABC139E] League

题意：

将有 \(N\) 个选手参加一场网球比赛。我们将称他们为 Player 1，Player 2，直到 Player N。

比赛采用循环赛制，总共将进行 \(\frac{N(N-1)}{2}\) 场比赛。是否可能安排这些比赛，以满足以下所有条件？

如果答案是肯定的，还要找出所需的最小天数。

• 每个选手一天最多进行一场比赛。
• 每个选手 \(i\)（\(1 \leq i \leq N\)）按照顺序与选手 \(A_{i,1}\)，\(A_{i,2}\)，...，\(A_{i,N-1}\) 进行一场比赛。

提示：可以同时进行比赛，但是一天只有举办一次比赛的时间。

输入格式： \[ \begin{array}{llll} N\\ A_{1,1} & A_{1,2} & \ldots & A_{1, N-1} \\ A_{2,1} & A_{2,2} & \ldots & A_{2, N-1} \\ : & & & \\ A_{N, 1} & A_{N, 2} & \ldots & A_{N, N-1} \end{array} \] 输出格式：

无解输出 \(-1\) ，否则输出答案。

数据范围：

\(3 \leq N \leq 1000,~1 \leq A_{i, j} \leq N,~A_{i, j} \neq i\) 且 \(A_{i,1},A_{i,2},\cdots,A_{i,N-1}\) 两两不同

对于连边 \(i \to A_{i,1}\) ，我们建立一个节点 \((i,A_{i,1})\) ，并向 \((i,A_{i,2})\) 连边，以此类推。

则原题有解当且仅当建出的图不存在环，并且答案即为拓扑排序后得到的最长链长度。

前者不难证明。后者证明不难，因为所有度数为 \(0\) 的节点都可以在一天内被删掉。

时间复杂度 \(\mathcal{O}(n^2)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e3 + 15))

int n,cnt,pos=1,head[N * N],in[N * N],t[N * N],g[N][N]; queue<int> q;
struct Edge{ int u,v,next; } e[N * N * 3];
int id(int x,int y) { if(x > y) swap(x, y); return (x - 1) * n + y; }
void addEdge(int u,int v) { e[++pos] = {u,v,head[u]}; head[u] = pos; ++in[v]; }
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n; int res = 0;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j < n; j++) cin >> g[i][j];
    for(int i = 1; i <= n; i++) {
        for(int j = 2; j < n; j++) {
            addEdge(id(i, g[i][j - 1]), id(i, g[i][j]));
        }
    }
    for(int i = 1; i <= n * n; i++) {
        if(!in[i]) { q.push(i); } t[i] = 1;
    }
    for(int u; !q.empty(); )
    {
        u = q.front(); q.pop(); up(res, t[u]);
        for(int i = head[u]; i; i = e[i].next) {
            int v = e[i].v; if(!(--in[v])) { q.push(v), t[v] = t[u] + 1; }
        }
    }
    for(int i = 1; i <= n * n; i++) if(in[i]) res = -1;
    cout << res << '\n';
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/blog/Lskkkno1/solution-at4893