题解 P6772 【[NOI2020]美食家】
万弘
2020-08-18 21:05:03
### Day1 T1 delicacy
给一个 $ n $ 个点的有向图,点有价值.有 $ m $ 条边,经过它要消耗 $ w_i $ 的时间.每次经过一个点时可以获得其价值(可重复获得).特别的,有 $ k $ 条形如 $ (t,x,y) $ 的活动,当 $ t $ 时刻在点 $ x $ 处时可额外获得 $ y $ 的价值.求在0时刻从点1出发,并在 $ T $ 时刻到点1能获得的最大价值.
$ n\le 50,T\le 10^9,k\le 200,1\le w_i\le 5 $
有启发性的两个subtask: $ T\le 52501; $ $ k=0 $
解:
对于 $ T\le 52501 $ ,直接dp即可.记 $ f(i,j) $ 表示 $ j $ 时刻在点 $ i $ 的最大价值.复杂度 $ \mathcal O(Tm) $
考虑用矩阵快速幂优化这一过程.记 $ R^T(i) $ 表示 $ T $ 时刻后在点 $ i $ 的最大价值,显然当 $ k=0 $ , $ R^T $ 是由 $ R^0 $ 乘上 $ T $ 个相同的转移矩阵得到的(这里的"乘"是广义矩阵乘法,即 $ C(i,j)=\max_kA(i,k)+B(k,j) $ ).考虑如何构造这个转移矩阵.
首先 $ 1\le w_i\le 5 $ ,我们可以将每个点 $ u $ 拆成5个,即 $ \{u+i\times n|0\le i\le 4\} $ , $ u+i\times n $ 表示相对于当前时刻, $ i $ 个时刻后的那个点.对于原图中的边 $ (u,v,w) $ ,让 $ u $ 向 $ v+(w-1)\times n $ 连边,边权为 $ v $ 的价值,即让转移矩阵 $ A(v+(w-1)\times n,u) $ 的值为 $ val(v) $ .另外每次转移后要将矩阵向上移动一个单位(这是我的理解),即要让 $ u+n\times (i-1) $ 向 $ u+n\times i $ 连边.矩阵加速即可,对于 $ k=0 $ ,复杂度为 $ \mathcal O(n^3\log T) $ .
对于一般情况,将活动按 $ t $ 排序,则相邻的两个活动构成 $ k=0 $ 的子问题.矩阵加速后令 $ R^t(x)+y $ 即可.复杂度 $ \mathcal O((wn)^3\log T\times k) $ .
这样是过不去的,但xyx神仙有高论:
> 你考虑矩阵相乘复杂度是立方没有办法,但是矩阵乘列向量复杂度是平方.你先暴力预处理那个转移矩阵的二次幂,然后拿列向量去乘他们就好了.
简单来说就是,先预处理 $ A^{2^i} $ ,复杂度 $ \mathcal O(n^3\log T) $ .之后再做矩阵加速时,不再用矩阵相乘,直接用列向量 $ R $ 去乘 $ A^{2^i} $ ,那么对于每对相邻的 $ t $ ,就只要 $ \mathcal O(n^2\log T) $ 了.总复杂度 $ \mathcal O(n^3\log T+n^2\log T\times k) $ .
```cpp
#define MAXN 255
ll res[MAXN][MAXN],a[31][MAXN][MAXN],t[MAXN][MAXN], n,m,T,k;
ll val[MAXN];
void mul(ll a[MAXN][MAXN],ll b[MAXN][MAXN],ll res[MAXN][MAXN],int n,int m,int p)
{
for(int i=1;i<=n;++i)
for(int j=1;j<=p;++j)
{
t[i][j]=a[i][1]+b[1][j];
for(int k=2;k<=m;++k)umax(t[i][j],a[i][k]+b[k][j]);
}
for(int i=1;i<=n;++i)
for(int j=1;j<=p;++j)res[i][j]=t[i][j];
}
struct tuple
{
int pos,t,ww;
bool operator <(const tuple& you)const{return t<you.t;}
}party[MAXN];
void pr()
{
puts("debug:");
for(int i=1;i<=5*n;++i)printf("%lld\n",res[i][1]);
}
void Qpow(int p)
{
// while(p--)mul(a[0],res,res,5*n,5*n,1),pr();
for(int i=30;i>=0;--i)
if(p&(1<<i))mul(a[i],res,res,5*n,5*n,1);
}
int main()
{
n=read(),m=read(),T=read(),k=read();
for(int i=1;i<=n;++i)val[i]=read();
for(int i=1;i<=5*n;++i)
for(int j=1;j<=5*n;++j)a[0][i][j]=res[i][j]=-1e17;
for(int i=1;i<=n;++i)
for(int j=1;j<=4;++j)a[0][i+n*(j-1)][i+n*j]=0;
res[1][1]=val[1];
for(int i=1;i<=m;++i)
{
int u=read(),v=read(),w=read()-1;
a[0][v+n*w][u]=val[v];
}
for(int i=1;i<=k;++i)party[i].t=read(),party[i].pos=read(),party[i].ww=read();
std::sort(party+1,party+k+1);
for(int i=1;i<=30;++i)mul(a[i-1],a[i-1],a[i],5*n,5*n,5*n);//n^3 log T
for(int i=1;i<=k;++i)
{
Qpow(party[i].t-party[i-1].t);
if(res[party[i].pos][1]>=0)res[party[i].pos][1]+=party[i].ww;
}
Qpow(T-party[k].t);
printf("%lld",max(-1ll,res[1][1]));
return 0;
}
```