拆点矩阵快速幂。

Before the Beginning

转载请将本段放在文章开头显眼处，如有二次创作请标明。

原文链接：https://www.codein.icu/lp6772/

前言

网上同步赛都没报上……随口胡的解法还是错的，晚上好不容易才补完T1。

题意

经过一条边需要花费的时间等于边权，每次到达一个点贡献都加上其点权，重复经过点重复算，且有 $k$ 次活动，若在 $t_i$ 时位于 $x_i$，则贡献加上 $y_i$，求时间 $T$ 后回到 $1$ 点，最大贡献。

解法

虽然第一眼看上去分层图，但 $T$ 的范围巨大，而边权极小，显然是不行的。
打了也许可以获得 20 pts 的部分分？
既然 $T$ 如此巨大，而点数也不大，可以考虑矩阵快速幂。
考虑所有边权为一时的特殊情况，显然构造转移矩阵$A$ ：$a(i,j) = c(j)$，随后走 $x$ 步即为乘上 $A^x$，初始时 $S = {c(1),-INF,-INF,\ldots}$。
而活动如何处理呢？不难想到拆成一段一段的乘上去，而在活动时处理答案矩阵 $S(1,x) += y$。
剩下的难点就是，如何将边权相等拓展到边权不等的情况。
缺乏智慧的我没有想明白，口胡了个错误解法，样例都过不了。
正确解法应该是拆点，将每个点拆成 $5$ 个点，记为 $num(i,1),num(i,2),\ldots,num(i,5)$，然后对于每条边权为 $w$ 的 $(u,w)$ 边：
$a(num(u,w),num(v,1)) = c(v)$ ，随后每个 $a(num(u,i-1),num(u,i)) = 0$。
形象地理解一下，从 $num(u,i)$ 走到 $num(u,i+1)$ 花费了一次乘法，即走了一步，积攒了一步的势能，而在 $num(u,w)$ 处释放掉，回到 $num(v,1)$ 的初始高度。
剩下的就是打代码了，有点卡常，可以预处理转移矩阵的 $2^i$ 次方，用倍增的方式计算出答案矩阵。

代码

人傻常数大，唉。
注意开 long long

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <ctype.h>
const int bufSize = 1e6;
using namespace std;
inline char nc()
{
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
template <typename T>
inline T read(T& r)
{
    static char c;
    r = 0;
    for (c = nc(); !isdigit(c); c = nc());
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r;
}
const int maxn = 260;
const long long INF = 1ll << 61;
int n, m, T, K;
int w[maxn], num[maxn][6], cnt;
struct Matrix
{
    int n, m;
    long long a[maxn][maxn];
    Matrix() {}
    Matrix(int n, int m, long long val)
    {
        this->n = n, this->m = m;
        for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) a[i][j] = val;
    }
    Matrix operator*(const Matrix b)
    {
        Matrix c(n, m, -INF);
        for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) for (int k = 1; k <= b.m; ++k)
            c.a[i][k] = max(c.a[i][k], a[i][j] + b.a[j][k]);
        return c;
    }
    void clear() { memset(a, ~0x3f, sizeof(a)); }

} G[40];
struct fes
{
    int x, y;
    long long t;
} F[maxn];
bool cmp(const fes a, const fes b) { return a.t < b.t; }
int main()
{
//    freopen("delicacy.in", "r", stdin);
//    freopen("delicacy.out", "w", stdout);
    read(n), read(m), read(T), read(K);
    for (int i = 1; i <= n; ++i) read(w[i]);
    G[0].clear();
    for (int i = 1; i <= n; ++i) num[i][1] = ++cnt;
    for (int i = 1; i <= m; ++i)
    {
        int u, v, t;
        read(u), read(v), read(t);
        if (!num[u][t])
        {
            for (int j = 2; j <= 5; ++j) num[u][j] = ++cnt;
            for (int j = 2; j <= 5; ++j) G[0].a[num[u][j - 1]][num[u][j]] = 0;
        }
        G[0].a[num[u][t]][v] = w[v];
    }
    G[0].n = G[0].m = cnt;
    for (int i = 1; i <= K; ++i) read(F[i].t), read(F[i].x), read(F[i].y);
    sort(F + 1, F + 1 + K, cmp);
    F[++K].t = T, F[K].x = 1, F[K].y = 0;
    long long maxt = 0;
    int maxx = 0;
    for (int i = 1; i <= K; ++i) maxt = max(maxt, F[i].t - F[i - 1].t);
    while ((1ll << maxx) < maxt) ++maxx;
    for (int i = 1; i <= maxx; ++i) G[i] = G[i - 1] * G[i - 1];
    Matrix now(1, cnt, -INF);
    now.a[1][1] = w[1];
    for (int i = 1; i <= K; ++i)
    {
        int dt = F[i].t - F[i - 1].t;
        for (int j = maxx; j >= 0; --j) if (dt & (1ll << j)) now = now * G[j];
        now.a[1][F[i].x] += F[i].y;
    }
    if (now.a[1][1] < 0) puts("-1");
    else printf("%lld\n", now.a[1][1]);
    return 0;
}