Liveddd's Blog

愛にできることはまだあるかい

LOJ#3339. 「NOI2020」美食家

发表于 更新于 分类于
本文字数： 2.8k 阅读时长 ≈ 6 分钟

一些小 trick。

注意到 $T$ 很大，并且 $n,m$ 都比较小，并且求的是恰好 $T$ 时刻。想到用矩阵快速幂来做。

如何处理路径长度？因为 $w_i$ 很小，我们可以考虑拆边，这样总点数是 $n+5m$ 的，不太能接受。实际上我们可以考虑拆点，这样总点数是 $5n$ 的，可以接受。另外还需要将点权转化为边权。

如何处理美食节？我们可以将美食节按照时间进行排序，每次计算时间之差内愉悦值变化，再加上美食节额外的愉悦值即可。

但是这样暴力快速幂做是 $\mathcal O(n^3k\log T)$ 的，无法通过所有数据。其实我们只需要保留矩阵的第一行即可。于是可以预处理原始矩阵的次幂，在求解过程中倍增计算。于是时间复杂度就降到了 $\mathcal O(n^3\log T+n^2k\log T)$。

Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N=250+10,M=5e2+10;
template<class T>
inline void read(T &x)
{
    x=0;int f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
struct Matrix
{
    int x,y;
    ll e[N][N];
    Matrix(){memset(e,-0x3f,sizeof(e));}
    friend Matrix operator*(const Matrix a,const Matrix b)
    {
        Matrix c;
        c.x=a.x,c.y=b.y;
        for(int i=1;i<=a.x;i++)
            for(int j=1;j<=b.y;j++)
                for(int k=1;k<=a.y;k++)
                    c.e[i][j]=max(c.e[i][j],a.e[i][k]+b.e[k][j]);
        return c;
    }
}f[50],ans;
struct Festival
{
    int t,x,y;
    friend bool operator<(const Festival a,const Festival b)
    {
        return a.t<b.t;
    }
}a[N];
int n,m,t,k;
int c[N];
int num(int i,int j)
{
    return (i-1)*5+j+1;
}
int main()
{
    freopen("delicacy.in","r",stdin);
    freopen("delicacy.out","w",stdout);
    read(n,m,t,k);
    for(int i=1;i<=n;i++)
        read(c[i]);
    for(int i=1;i<=n;i++)
        for(int j=0;j<=3;j++)
            f[0].e[num(i,j)][num(i,j+1)]=0;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        read(u,v,w);
        f[0].e[num(u,w-1)][num(v,0)]=c[v];
    }
    f[0].x=5*n,f[0].y=5*n;
    for(int i=1;i<=31;i++)
        f[i]=f[i-1]*f[i-1];
    
    for(int i=1;i<=k;i++)
        read(a[i].t,a[i].x,a[i].y);
    sort(a+1,a+1+k);
    a[0]=(Festival){0,0,0};
    a[k+1]=(Festival){t,0,0};
    ans.e[1][1]=c[1];
    ans.x=1,ans.y=5*n;
    for(int i=1;i<=k+1;i++)
    {
        int d=a[i].t-a[i-1].t;
        for(int i=31;~i;i--)
            if(d>>i&1)
                ans=ans*f[i];
        ans.e[1][num(a[i].x,0)]+=a[i].y;
    }
    if(ans.e[1][1]>=0)
        printf("%lld\n",ans.e[1][1]);
    else printf("-1\n");
    return 0;
}