题解 P6772 【[NOI2020]美食家】
xukuan
2020-08-25 22:22:17
**注意：本篇题解中的代码只能在64-bit的电脑上运行，具体原因未知。以Windows Dev_C++为例，编译选项请选择TDM-GCC 一串数字 64-bit Release,而不是TDM-GCC 一串数字 32-bit Release**
**另外，由于不同网站评测机常数性能差异，部分常数较大的代码不能在洛谷上通过，本题建议有条件的同学使用XJOI开发版等其他较快的OJ测试**
看完这题没什么思路，再看数据范围
$0 \leq k \leq 200,1 \leq T \leq 10^9,1 \leq w_i \leq 5$
k和T的数据范围告诉我们这题要对转移用压缩处理，而$w_i$出奇的小：如果大家对[这题](https://www.luogu.com.cn/problem/P2886)有印象的话，就会发现：如果对于任意的$i$满足$w_i=1$，那么这两题是一样的。但是这题要记得边权转点权，最后答案加上$c_1$
很快我们会想到拆边，即对任意一条边$(x_i,y_i,z_i)$，把他拆成$(x_i,e_{i,1},0),(e_{i,1},e_{i,2},0),...,(e_{z_{i-1}},y_i,c_{x,i})$
这样的时间复杂度是$O(k(n+\sum_{i=1}^mw_i)^3log_2T) \leq O(k(n+4m)^3log_2T)$，只有45分
我们会发现，不论在何时，当$x_i$相同时，$e_{i,j}$的值都是相同的。所以我们可以把拆边变成拆点，即先预处理出$(i,e_{i,1},0),(e_{i,1},e_{i,2},0),(e_{i,2},e_{i,3},0),(e_{i,3},e_{i,4},0)$，然后连边时直接$(e_{x_i,z_i-1},y_i,c_{x_i})$，其中$e_{i,0}=x_i$
时间复杂度降到$O(k(5n)^3log_2T)$，35分，还是不够
对于矩阵快速幂：类似多重背包或完全背包的那个优化，考虑预处理出所有2的幂次，在询问的时候直接乘上去。
时间复杂度降到$O(k(5n)^3)$，55分，继续优化
**最重要的优化：我们发现我们对于矩阵快速幂的结果，真正有用的其实只有第一行，所以转移的时候后面的直接不选，时间复杂度降到$O(k(5n)^2log_2T)$，写的漂亮能过**
代码：
```cpp
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const ll N=260,INF=1ll<<60;
ll n,m,T,K,cnt,a[N],id[N][10];
struct matrix{
ll mat[N][N];
matrix(){memset(mat,-0x3f,sizeof(mat));}
}G[30];
struct node{
ll QAQ[N];
node(){memset(QAQ,-0x3f,sizeof(QAQ));}
}f[N];
struct GG{
ll t,x,val;
}b[N];
inline ll read(){
ll x=0,tmp=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') tmp=-1;
ch=getchar();
}
while(isdigit(ch)){
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return tmp*x;
}
inline matrix floyd(matrix a,matrix b){
matrix c;
for(ll k=1; k<=cnt; k++){
for(ll i=1; i<=cnt; i++){
for(ll j=1; j<=cnt; j++) c.mat[i][j]=max(c.mat[i][j],a.mat[i][k]+b.mat[k][j]);
}
}
return c;
}
inline node mul(node a,matrix b){
node c;
for(ll k=1; k<=cnt; k++){
for(ll j=1; j<=cnt; j++) c.QAQ[j]=max(c.QAQ[j],a.QAQ[k]+b.mat[k][j]);
}
return c;
}
inline node ksm(node x,ll y){
for(ll i=0; (1<<i)<=y; i++){
if(y&(1<<i)) x=mul(x,G[i]);
}
return x;
}
inline bool cmp(GG a,GG b){
return a.t<b.t;
}
int main(){
cnt=n=read(); m=read(); T=read(); K=read();
for(ll i=1; i<=n; i++) a[i]=read();
for(ll i=1; i<=n; i++){
id[i][0]=i;
for(ll j=1; j<=4; j++){
id[i][j]=++cnt;
G[0].mat[id[i][j-1]][id[i][j]]=0;
}
}
while(m--){
ll x=read(),y=read(),z=read();
G[0].mat[id[x][z-1]][y]=max(G[0].mat[id[x][z-1]][y],a[x]);
}
for(ll i=1; (1<<i)<=T; i++) G[i]=floyd(G[i-1],G[i-1]);
for(ll i=1; i<=K; i++){
b[i].t=read();
b[i].x=read();
b[i].val=read();
}
b[++K].t=T;
sort(b+1,b+1+K,cmp);
f[0].QAQ[1]=0;
for(ll i=1; i<=K; i++){
f[i]=ksm(f[i-1],b[i].t-b[i-1].t);
if(b[i].x) f[i].QAQ[b[i].x]+=b[i].val;
}
if(f[K].QAQ[1]<0) cout<<"-1";
else cout<<f[K].QAQ[1]+a[1]<<endl;
return 0;
}
```