Early's Blog

Hello, World!

0%

「NOI2020」美食家

发表于 分类于
本文字数： 2.8k

题目链接

题意

给定一个 nn 个点、mm 条有向边的图，点有点权，边有通过这条边所用的时间，不能在点上停留。每次到达一个点都会获得相当于点权的贡献。另外有 kk 个事件，每个均描述了第 tt 天编号为 xx 的点权值会增加 vv。最大化从 11 号点出发、在 TT 天后回到 11 的总贡献。

思路

先考虑 k=0k=0 的情况。

发现 n≤50n\leq50，边权 w≤5w\leq5，根据 「SCOI2009」迷路 的思路，我们可以把每个点拆成 max⁡w\max w 个点，建出（伪）矩阵跑快速幂。

然后发现对于每个事件 ii，都可以把上一个事件的结果乘上边矩阵的 ti−ti−1t_i-t_{i-1} 次幂，然后在结果上将第 xix_i 点加上 vv。

这是分段快速幂的思路，时间复杂度 O((nw)3log⁡T+k⋅(nw)2log⁡T)O\left((nw)^3\log T+k\cdot(nw)^2\log T\right)。

实现

注意最后结果还要乘上边矩阵的 T−tkT-t_k 次幂。

代码

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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=50,K=200,W=5,LT=29,MSIZ=N*W;
int n,m,T,k,c[N+1];
int msiz,id[N+1][W];
struct matrix {
    long long m[MSIZ+1][MSIZ+1];
    matrix()
    {
        memset(m,0xc0,sizeof(m));
        return;
    }
    inline long long *operator [](int i)
    {
        return m[i];
    }
};
matrix p[LT+1];
struct festival {
    int tim,pos,val;
};
festival fes[K+2];
long long *res;
int read()
{
    int ret=0;
    char c=getchar();
    while(!isdigit(c)) {
        c=getchar();
    }
    while(isdigit(c)) {
        ret=ret*10+c-'0';
        c=getchar();
    }
    return ret;
}
matrix operator *(matrix x,matrix y)
{
    matrix ret;
    for(int i=1;i<=msiz;++i) {
        for(int j=1;j<=msiz;++j) {
            for(int k=1;k<=msiz;++k) {
                ret[i][j]=max(ret[i][j],x[i][k]+y[k][j]);
            }
        }
    }
    return ret;
}
long long *operator *(long long x[],matrix y)
{
    long long *ret=new long long [MSIZ+1];
    memset(ret,0xc0,sizeof(long long)*(MSIZ+1));
    for(int i=1;i<=msiz;++i) {
        for(int j=1;j<=msiz;++j) {
            ret[i]=max(ret[i],x[j]+y[j][i]);
        }
    }
    return ret;
}
int main()
{
    freopen("delicacy.in","r",stdin);
    freopen("delicacy.out","w",stdout);
    n=read(),m=read(),T=read(),k=read();
    for(int i=1;i<=n;++i) {
        c[i]=read();
    }
    for(int i=1;i<=n;++i) {
        id[i][0]=++msiz;
    }
    while(m--) {
        int u=read(),v=read(),w=read();
        for(int i=1;i<w;++i) {
            if(!id[u][i]) {
                id[u][i]=++msiz;
            }
        }
        for(int i=1;i<w;++i) {
            p[0][id[u][i-1]][id[u][i]]=0;
        }
        p[0][id[u][w-1]][v]=c[v];
    }
    for(int i=1;i<=k;++i) {
        fes[i]=festival{read(),read(),read()};
    }
    sort(fes+1,fes+k+1,[](const festival x,const festival y) {
        return x.tim<y.tim;
    });
    fes[k+1]=festival{T};
    for(int i=1;i<=LT;++i) {
        p[i]=p[i-1]*p[i-1];
    }
    res=new long long[MSIZ+1];
    memset(res,0xc0,sizeof(long long)*(MSIZ+1));
    res[1]=c[1];
    for(int i=1;i<=k+1;++i) {
        int dt=fes[i].tim-fes[i-1].tim;
        for(int j=LT;~j;--j) {
            if(dt&1<<j) {
                res=res*p[j];
            }
        }
        res[id[fes[i].pos][0]]+=fes[i].val;
    }
    printf("%lld\n",res[id[1][0]]>0?res[id[1][0]]:-1);
    return 0;
}