题解 P6772 [NOI2020] 美食家

观察数据范围，\(T\) 很大，\(n\) 很小，用矩乘。

对于一条边 \((u,v,w)\)，我们将 \(u\) 拆成 \(w-1\) 个点，并连接 \((u_0,u_1,0),(u_1,u_2,0)...(u_{w-2},u_{w-1},0)\) 和 \((u_{w-1},v_0,c_{v})\)，总点数 \(5n\)。

将美食节按时间排序，相邻两个美食节之间用矩阵快速幂转移，然后再加上附加贡献，复杂度 \(O((5n)^3\cdot \log T\cdot k)\)，会 T。

考虑倍增预处理，定义 \(B_{i}=A^i\)，复杂度 \(O((5n)^3\cdot \log T)\)。每次转移时直接倍增，因为其中一个退化成向量，所以复杂度 \(O((5n)^2\cdot k\cdot \log T)\)。

code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=250+5,inf=LLONG_MAX/2;
struct node{
  int n,m;ll a[N][N];
  node(){for(int i=0;i<N;++i)for(int j=0;j<N;++j)a[i][j]=-inf;}
}A[31],ans;
struct node2{int t,x,y;}b[N];
int n,m,T,k,c[N],id[N][10],tot=0;
bool cmp(node2 x,node2 y){return x.t<y.t;}
node operator*(const node &x,const node &y){
  node res;
  res.n=x.n;res.m=y.m;
  for(int i=1;i<=res.n;++i)for(int j=1;j<=res.m;++j)for(int k=1;k<=x.m;++k)res.a[i][j]=max(res.a[i][j],x.a[i][k]+y.a[k][j]);
  return res;
}
int main(){
  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  cin>>n>>m>>T>>k;for(int i=1;i<=n;++i){cin>>c[i];id[i][0]=++tot;}
  for(int i=1;i<=m;++i){
    int u,v,w;cin>>u>>v>>w;
    for(int j=1;j<w;++j)if(!id[u][j])id[u][j]=++tot;
    for(int j=1;j<w;++j)A[0].a[id[u][j-1]][id[u][j]]=0;
    A[0].a[id[u][w-1]][v]=c[v];
  }
  A[0].n=A[0].m=tot;
  for(int i=1;i<=30;++i)A[i]=A[i-1]*A[i-1];
  for(int i=1;i<=k;++i)cin>>b[i].t>>b[i].x>>b[i].y;
  sort(b+1,b+k+1,cmp);
  b[k+1].t=T;ans.n=1;ans.m=tot;ans.a[1][1]=c[1];
  for(int i=0;i<=k;++i){
    int tim=b[i+1].t-b[i].t;
    for(int j=0;j<=30;++j)if((tim>>j)&1)ans=ans*A[j];
    ans.a[1][b[i+1].x]+=b[i+1].y;
  }
  if(ans.a[1][1]<0)cout<<-1<<endl;
  else cout<<ans.a[1][1]<<endl;
  return 0;
}