Description

题目链接

题目大意：给定 $n$ 个点 $m$ 条边的有向图，第 $i$ 条边在时间 $i$ 加入。给定 $L$，对每个点 $x$ 求最早在什么时候存在一条从 $1$ 到 $x$ 长度为 $L$ 的路径，不存在时答案为 $-1$。

Solution

这种在图上恰好长度为 $L$ 的描述很容易让人想起矩阵乘法。

如果我们令 $f(i, j)$ 表示从 $1$ 出发，经过 $j$ 条边到达 $i$ 的最早时间，$w_{i, j}$ 为边 $i \to j$ 被加入的最早时间，可以得到转移 $f(i, j) = \min \limits_{1 \le k \le n} \max \{f(k, j - 1), w_{k, i}\}$。

写成矩阵乘法的形式：

$$ \begin{bmatrix} f(1, j) \\ f(2, j) \\ f(3, j) \\ \vdots \\ f(n, j) \\ \end{bmatrix} = \begin{bmatrix} w_{1, 1}, w_{2, 1}, \cdots, w_{n, 1} \\ w_{1, 2}, w_{2, 2}, \cdots, w_{n, 2} \\ w_{1, 3}, w_{2, 3}, \cdots, w_{n, 3} \\ \ddots \\ w_{1, n}, w_{2, n}, \cdots, w_{n, n} \\ \end{bmatrix} \begin{bmatrix} f(1, j - 1) \\ f(2, j - 1) \\ f(3, j - 1) \\ \vdots \\ f(n, j - 1) \end{bmatrix} $$

这个东西可以用矩阵快速幂计算。

时间复杂度 $O(n^3 \log L)$。

Code

#include <bits/stdc++.h>

template <class T>
inline void read(T &x) {
    x = 0;
    int f = 0;
    char ch = getchar();
    while (!isdigit(ch))    { f |= ch == '-'; ch = getchar(); }
    while (isdigit(ch))     { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    x = f ? -x : x;
    return ;
}

typedef unsigned long long uLL;
typedef long long LL;

struct Matrix {
    LL a[110][110];
    int n;
    
    Matrix() {
        memset(a, 0x7f, sizeof(a));
        n = 0;
    }
    
    friend Matrix operator * (const Matrix &a, const Matrix &b) {
        Matrix c;
        c.n = a.n;
        for (int k = 1; k <= a.n; ++k) {
            for (int i = 1; i <= a.n; ++i) {
                for (int j = 1; j <= a.n; ++j) {
                    c.a[i][j] = std::min(c.a[i][j], std::max(a.a[i][k], b.a[k][j]));
                }
            }
        }
        return c;
    }
} g;

int n, m, L;

Matrix qPow(Matrix a, int b) {
    Matrix s;
    for (int i = 1; i <= n; ++i)    s.a[i][i] = 1;
    s.n = a.n;
    while (b) {
        if (b & 1)    s = s * a;
        a = a * a, b >>= 1;
    }
    return s;
}

int main() {
    read(n), read(m), read(L);
    g.n = n;
    for (int i = 1, u, v; i <= m; ++i) {
        read(u), read(v);
        g.a[u][v] = i;
    }
    Matrix ans = qPow(g, L);
    for (int i = 1; i <= n; ++i)    printf("%lld ", ans.a[1][i] > m ? -1 : ans.a[1][i]);
    puts("");
    return 0;
}