见 此笔记 第7部分。

题目链接-LOJ

（别问我为什么不放 AcWing 的链接，因为我这题 LOJ 上过了但是 AcWing 上 TLE了……）

题意

有 $n$ 个城市，$1\sim n$ 编号，$i$ 能提供 $c_i$ 的愉悦值。有 $m$ 条单向道路，道路 $i$ 起始为 $u_i,v_i$ ，花费 $w_i$ 天（经过之后天数+=$w_i$）。

计划进行为期 $T$ 天的旅行，第 $0$ 天从 $1$ 出发，$T$ 天后恰好回到 $1$ 。每到达（包括起始点）一个城市会获得当地的愉悦值，且多次到达可以累加。中途不能停留。

有 $k$ 个不同时间的节日，$i$ 次在 $t_i$ 天于 $x_i$ 举办，如果当时在这个城市会额外得到 $y_i$.

求愉悦值之和的最大值。

$1\leq n\leq 50，n \leq m \leq 50,0 \leq k \leq 200,1\leq t_i \leq T \leq 10^9,1 \leq w_i \leq 5$

思路

开始了.jpg （然而这已经是最后一题了！）

拆点，DP，矩乘，倍增优化

这类问题的解决方式（总结）

首先是描述：边有边权，问从 i 出发恰好过 k 条边到 j 的最长路

$f[k,i,j]$ 表示上述意义，设邻接矩阵为 $g$ ，得到转移：
$$ f[k,i,j]=max_p\{f[k-1,i,p]+g_{p,j}\} $$
定义一个广义矩阵乘法：
$$ C_{i,j}=max_k\{A_{i,k}+B_{k,j}\} $$
然后把 $f[k]$ 看做一个矩阵，可以改写上式为：
$$ f[k]=f[k-1]\times g $$
根据结合律（证明略），有
$$ f[k]=f[0]\times g^k $$
于是得到了 $O(n^3\log k)$ 的优良复杂度，结合倍增等方式能进一步优化。

回归题目。

首先，本题中是点权不是边权。那么把每个点的点权作为所有入边的边权，特判起始点点权。($f[0][1][1]=c_1$)

其次，每条边是当 $w_i$ 条计时的，$w_i\leq 5$ ，考虑拆点。边 $e$ 拆分成若干点 $e_i$ 表示在这条边上的 $i$ 天。那么 $e=(u,v,w)=> (u,e_1,0),…,(e_{w-2},e_{w-1},0),(e_{w-1},v,c_v)$

最后，考虑如何处理 $k$ 个美食节。在时间相邻的两个美食节之间，乘 $g$ 转移，然后在美食节那天乘上一个举办城市入边边权加了 $y$ 的转移矩阵即可。

但是这样子点数是 $n+4m$ ，还是过不去。

考虑更换拆边为拆点，对于 $u\to v=w$ 这个过程，看做 $u$ 待了 $w-1$ 天，第一天获得点权，在 $w$ 天到达 $v$ ，每个点 $u$ 拆成 “待在 u 的第 i 天即可，点数 $5n$.

朴素实现 $O((5n)^3k\log t)$ ，由于最后只和 $f[T,1,1]$ 有关， $f[k]$ 保留第一行即可，再预处理 $g^{2^k}$ 就可以通过本题。时间复杂度 $O((5n)^3\log T+(5n)^2k\log T).$

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=250+10,K=200+10;
int n,m,T,k,c[N],id[N][6],tot;
ll A[N];

struct node
{
        int time,x,y;
        bool operator < ( node tmp ) { return time<tmp.time; }
}t[K];
struct matrix
{
        ll s[N][N];
        matrix() { memset( s,0xc0,sizeof(s) ); }
        ll * operator [] ( int x ) { return s[x]; }
        matrix operator * ( matrix tmp )
        {
                matrix c;
                for ( int i=1; i<=tot; i++ )
                 for ( int k=1; k<=tot; k++ )
                 {
                         if ( s[i][k]<0 ) continue;
                         for ( int j=1; j<=tot; j++ )
                                c[i][j]=max( c[i][j],s[i][k]+tmp[k][j] );
                 }
                return c;
        }
}D[35];

void mul( matrix T )
{
        ll B[N];
        for ( int i=1; i<=tot; i++ )
                B[i]-=4e18;
        for ( int k=1; k<=tot; k++ )
        {
                if ( A[k]<0 ) continue;
                for ( int j=1; j<=tot; j++ )
                        B[j]=max( B[j],A[k]+T[k][j] );
        }
        for ( int i=1; i<=tot; i++ )
                A[i]=B[i];
}

int main()
{
        freopen( "delicacy.in","r",stdin ); freopen( "delicacy.out","w",stdout );

        scanf( "%d%d%d%d",&n,&m,&T,&k ); tot=n;
        for ( int i=1; i<=n; i++ )
                id[i][0]=i;
        for ( int i=1; i<=n; i++ )
                scanf( "%d",&c[i] );
        for ( int i=1,u,v,w; i<=m; i++ )
        {
                scanf( "%d%d%d",&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++ )
                        D[0][id[u][j-1]][id[u][j]]=0;
                D[0][id[u][w-1]][v]=c[v];
        }
        for ( int i=1,t1,t2,t3; i<=k; i++ )
                scanf( "%d%d%d",&t1,&t2,&t3 ),t[i]=(node){t1,t2,t3};

        sort( t+1,t+1+k ); t[0]=(node){0,0,0}; t[k+1]=(node){T,0,0};
        for ( int i=1; i<=30; i++ )
                D[i]=D[i-1]*D[i-1];
        for ( int i=2; i<=tot; i++ )
                A[i]=-4e18;
        A[1]=c[1];
        for ( int i=1; i<=k+1; i++ )
        {
                int del=t[i].time-t[i-1].time;
                for ( int j=30; ~j; j-- )
                        if ( del & (1<<j) ) mul( D[j] );
                A[t[i].x]+=t[i].y;
        }

        if ( A[1]<0 ) printf( "-1" );
        else printf( "%lld",A[1] );

        fclose( stdin ); fclose( stdout );
}