[NOI2020D1T1]美食家 题解
本文最后更新于 151 天前,其中的信息可能已经有所发展或是发生改变。

拆点矩阵快速幂

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;
}
本文标题:[NOI2020D1T1]美食家 题解
本文作者:Clouder
本文链接: https://www.codein.icu/lp6772/
转载请标明。
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇