摘要:转移矩阵拆点解决图论问题

「NOI2020」美食家

题面

题目分析

今年noi的题啊,同步赛上直接打的阶乘狂暴…

题目要求的是从起点出发经过$T$的时间后的最长路.

先简化问题,边权均为$1$,那么就是经过$T$条边的最长路,可以写出dp:

其中$G$为邻接矩阵,那么我们可以定义一个矩阵运算表示上述过程:

那么dp的转移就可以写为:

我们定义的运算容易发现是满足结合律的,所以可以用矩阵的幂次表示:

这样就可以矩阵快速幂了.

回到原题,边权不为$1$显然不能只能套用上述做法,然而$1\leq w_i \leq 5$,这启发我们对点进行拆点.

具体地来说,点$u$连向点$v$的长度为$w$的边,我们可以将其视为在$u$拆出的点中滞留了$w$次,最后一次到达$v$,并将点权转化到最后一次的连边上.

因为我们只关心从$1$号点出发的情况,所以用一个向量(矩阵的第一行)去乘矩阵来降低算法常数.

对于题目中的节日,我们可以在节日的间隔之间用矩阵乘法进行转移,然后在求得的向量的对应点上加上节日带来的额外贡献.

代码

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
#include "iostream"
#include "cstdlib"
#include "cstdio"
#include "cstring"
#include "cmath"
#include "cctype"
#include "ctime"
#include "iomanip"
#include "algorithm"
#include "set"
#include "queue"
#include "map"
#include "stack"
#include "deque"
#include "vector"
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%lld\n",x)
#define debugi(x) printf("debug:%d\n",x)
#define debugf(x) printf("debug:%llf\n",x)
#define endl putchar('\n')
typedef long long lxl;
const lxl small=5,big=51,large=251;
lxl n,m,T,k,tot;
lxl c[big],id[big][small],A[large],B[large];
struct _Matrix
{
lxl a[large][large];
_Matrix(){memset(a,0xc0,sizeof a);}
inline lxl* operator [](const lxl i){return a[i];}
inline _Matrix operator *(const _Matrix &another)const
{
_Matrix B;
R int i,k,j;
for(i=1;i<=tot;++i)
for(k=1;k<=tot;++k)
{
if(a[i][k]<0)continue;
for(j=1;j<=tot;++j)
B.a[i][j]=std::max(B.a[i][j],a[i][k]+another.a[k][j]);
}
return B;
}
}Q[31];
struct _Festival
{
lxl t,x,w;
inline bool operator <(const _Festival &another)const{return t<another.t;}
}f[large];
inline lxl read()
{
char c(getchar());
lxl f(1),x(0);
for(;!isdigit(c);(c=='-')&&(f=-1),c=getchar());
for(;isdigit(c);x=(x<<1)+(x<<3)+(c^48),c=getchar());
return f*x;
}
inline void VectorMulMatrix(_Matrix C)
{
memset(B,0xc0,sizeof B);
for(R int k(1);k<=tot;++k)
{
if(A[k]<0)continue;
for(R int j(1);j<=tot;++j)
B[j]=std::max(B[j],A[k]+C[k][j]);
}
memcpy(A,B,sizeof A);
}
int main(void)
{
memset(A,0xc0,sizeof A);
n=read(),m=read(),T=read(),k=read();
for(R int i(1);i<=n;++i)c[i]=read();
A[1]=c[1];
for(R int i(1);i<=n;++i)id[i][0]=++tot;
for(R int i(1);i<=m;++i)
{
lxl u=read(),v=read(),w=read();
for(R int j(1);j<w;++j)if(!id[u][j])id[u][j]=++tot;
for(R int j(1);j<w;++j)Q[0][id[u][j-1]][id[u][j]]=0;
Q[0][id[u][w-1]][id[v][0]]=c[v];
}
for(R int i(1);i<=k;++i)f[i].t=read(),f[i].x=read(),f[i].w=read();
std::sort(f+1,f+1+k);
f[0]={0,0,0},f[k+1]={T,0,0};
for(R int i(1);i<=30;++i)Q[i]=Q[i-1]*Q[i-1];
for(R int i(1);i<=k+1;++i)
{
lxl tim=f[i].t-f[i-1].t;
for(R int j(30);~j;--j)if((tim>>j)&1)VectorMulMatrix(Q[j]);
A[f[i].x]+=f[i].w;
}
printf(A[1]<0?"-1\n":"%lld\n",A[1]);
return 0;
}