P6772 [NOI2020] 美食家

训练角度：图上的状态转移，倍增

→ \rightarrow

→ 优化状态转移；

▍ 题意

精灵王国共有

n n

n 座城市，城市从

1 1

1 到

n n

n 编号，其中城市

i i

i 的美食能为小 W 提供

c i c_i

c

i

​

的愉悦值。精灵王国的城市通过

m m

m 条 单向道路 连接，道路从

1 1

1 到

m m

m 编号，其中道路

i i

i 的起点为城市

u i u_i

u

i

​

，终点为城市

v i v_i

v

i

​

，沿它通行需要花费

w i w_i

w

i

​

天。也就是说，若小 W 在第

d d

d 天从城市

u i u_i

u

i

​

沿道路

i i

i 通行，那么他会在第

d + w i d + w_i

d

w

i

​

天到达城市

v i v_i

v

i

​

。

小 W 计划在精灵王国进行一场为期

T T

T 天的旅行，更具体地：他会在第

0 0

0 天从城市

1 1

1 出发，经过

T T

T 天的旅行，最终在 **恰好第

T T

T 天** 回到城市

1 1

1 结束旅行。由于小 W 是一位美食家，每当他到达一座城市时（包括第

0 0

0 天和第

T T

T 天的城市

1 1

1 ），他都会品尝该城市的美食并获得其所提供的愉悦值，若小 W 多次到达同一座城市，他将 获得多次愉悦值 。注意旅行途中小 W 不能在任何城市停留 ，即当他到达一座城市且还未结束旅行时，他当天必须立即从该城市出发前往其他城市。

对于上图，小 W 一种为期

11 11

11 天的可行旅游方案为

1 → 2 → 1 → 2 → 3 → 1 1 \to 2 \to 1 \to 2 \to 3 \to 1

1

→

2

→

1

→

2

→

3

→

1 ：

• 第

  0 0

  0 天，小 W 从城市

  1 1

  1 开始旅行，获得愉悦值

  1 1

  1 并向城市

  2 2

  2 出发。

• 第

  1 1

  1 天，小 W 到达城市

  2 2

  2 ，获得愉悦值

  3 3

  3 并向城市

  1 1

  1 出发。

• 第

  4 4

  4 天，小 W 到达城市

  1 1

  1 ，获得愉悦值

  1 1

  1 并向城市

  2 2

  2 出发。

• 第

  5 5

  5 天，小 W 到达城市

  2 2

  2 ，获得愉悦值

  3 3

  3 并向城市

  3 3

  3 出发。

• 第

  7 7

  7 天，小 W 到达城市

  3 3

  3 ，获得愉悦值

  4 4

  4 并向城市

  1 1

  1 出发。

• 第

  11 11

  11 天，小 W 到达城市

  1 1

  1 ，获得愉悦值

  1 1

  1 并结束旅行。

• 小 W 在该旅行中获得的愉悦值之和为

  13 13

  13 。

此外，精灵王国会在 不同 的时间举办

k k

k 次美食节。具体来说，第

i i

i 次美食节将于第

t i t_i

t

i

​

天在城市

x i x_i

x

i

​

举办，若小 W 第

t i t_i

t

i

​

天时恰好在城市

x i x_i

x

i

​

，那么他在品尝城市

x i x_i

x

i

​

的美食时会 额外得到

y i y_i

y

i

​

的愉悦值。现在小 W 想请作为精灵王国接待使者的你帮他算出，他在旅行中能获得的愉悦值之和的 最大值 。

输入格式

从标准输入中读入数据。

第一行四个整数

n , m , T , k n, m, T, k

n

,

m

,

T

,

k ，依次表示城市数、道路条数、旅行天数与美食节次数。

第二行

n n

n 个整数

c i c_i

c

i

​

，表示每座城市的美食所能提供的愉悦值。接下来

m m

m 行每行三个整数

u i , v i , w i u_i, v_i, w_i

u

i

​

,

v

i

​

,

w

i

​

，依次表示每条道路的起点、终点与通行天数。

最后

k k

k 行每行三个整数

t i , x i , y i t_i, x_i, y_i

t

i

​

,

x

i

​

,

y

i

​

，依次表示每次美食节的举办时间、举办城市与提供的额外愉悦值。

本题中数据保证：

• 对所有

  1 ≤ i ≤ m 1 \leq i \leq m

  1

  ≤

  i

  ≤

  m ，有

  u i ≠ v i u_i\neq v_i

  u

  i

  ​

  

  =

  v

  i

  ​

  。但数据中可能存在路线重复的单向道路，即可能存在

  1 ≤ i < j ≤ m ，使得 u i

  u j , v i

  v j 1 \leq i < j \leq m，使得 u_i = u_j, v_i = v_j

  1

  ≤

  i

  <

  j

  ≤

  m

  ，使得

  u

  i

  ​

  =

  u

  j

  ​

  ,

  v

  i

  ​

  =

  v

  j

  ​

  。

• 对每座城市都满足：至少存在一条以该该城市为起点的单向道路。

• 每次美食节的举办时间

  t i t_i

  t

  i

  ​

  互不相同。

输出格式

输出到标准输出中。

仅一行一个整数，表示小 W 通过旅行能获得的愉悦值之和的最大值。

**若小 W 无法在第

T T

T 天回到城市

1 1

1 ，则输出

− 1 -1

−

1** 。

测试点约束

对于所有测试点：

1 ≤ n ≤ 50 1 \leq n \leq 50

1

≤

n

≤

50 ，

n ≤ m ≤ 501 n \leq m \leq 501

n

≤

m

≤

501 ，

0 ≤ k ≤ 200 0 \leq k \leq 200

0

≤

k

≤

200 ，

1 ≤ t i ≤ T ≤ 1 0 9 1 \leq t_i \leq T \leq 10^9

1

≤

t

i

​

≤

T

≤

1

0

9 。

1 ≤ w i ≤ 5 1 \leq w_i \leq 5

1

≤

w

i

​

≤

5 ，

1 ≤ c i ≤ 52501 1 \leq c_i \leq 52501

1

≤

c

i

​

≤

52501 ，

1 ≤ u i , v i , x i ≤ n 1 \leq u_i, v_i, x_i \leq n

1

≤

u

i

​

,

v

i

​

,

x

i

​

≤

n ，

1 ≤ y i ≤ 1 0 9 1 \leq y_i \leq 10^9

1

≤

y

i

​

≤

1

0

9 。

每个测试点的具体限制见下表：

题目分析

问题建模

本题的核心是求解在特定时间约束下（恰好

T T

T 天返回起点）的 最长路径问题 ，并处理多个时间点上的权值增益（美食节）。由于天数规模可达 1e9，直接逐天模拟不可行，需结合图论与动态规划进行高效求解。

算法思路

采用 倍增法（Binary Lifting） 与 动态规划（DP） 结合，核心步骤包括：

1. 状态扩展（拆点）

   将每个城市拆分为

   ( w i ≤ 5 )   5 ( w_i \le 5 ) \ 5

   (

   w

   i

   ​

   ≤

   5

   )

   5 个状态（对应道路通行时间

   1 ∼ 5 1 \sim 5

   1

   ∼

   5 天），通过状态转移表示 “剩余行走天数”。

   • 例如：城市

     u u

     u 的拆分点为 u * 5 - 5 + w ，其中 w 表示还需

     w w

     w 天才能完成当前道路（如下图）。

2. 预处理倍增矩阵

   定义 f[d][i][j] 表示从状态

   i i

   i 到

   j j

   j 经过

   2 d 2^d

   2

   d 天的最大愉悦值。利用矩阵广义乘法（取 max 和加法）预处理所有可能的

   2 d 2^d

   2

   d 天转移。

3. 分段处理时间轴

   将整个

   T T

   T 天分割为多个区间（以美食节为分界点），逐个区间应用倍增矩阵快速计算状态转移，并在美食节时间点更新额外权值。

关键步骤解析

1. 拆点建模

• 动机 ：处理道路通行时间

  w i w_i

  w

  i

  ​

  （最多

  5 5

  5 天）带来的多日转移问题。

• 方法 ：每个城市拆分为

  5 5

  5 个状态，表示当前停留的 “剩余天数”。

  • 例如：道路

    u → v u \rightarrow v

    u

    →

    v 耗时

    3 3

    3 天，对应

    u u

    u 的初始状态转移到

    v v

    v 的第

    2 2

    2 个拆分点（还需

    2 2

    2 天才能获得愉悦值）。

// 建边示例：u → v 耗时 w 天
int newU = u * 5 - 5;          // u 的初始拆分点（剩余 0 天）
int newV = v * 5 - 5 + w - 1;  // v 的拆分点（剩余 w-1 天）
f[0][newU][newV] = (w == 1 ? c_v : 0); // 若 w=1 直接获得愉悦值

2. 倍增矩阵预处理

• 状态转移方程 ：

  f[d][i][j] = max{ f[d-1][i][k] + f[d-1][k][j] }

  表示通过

  2 d − 1 2^{d-1}

  2

  d

  −

  1 天的转移组合成

  2 d 2^d

  2

  d 天的转移。

• 时间复杂度 ：

  O ( l o g D × n 3 ) O(log D \times n^3)

  O

  (

  l

  o

  g

  D

  ×

  n

  3

  ) ，其中

  n n

  n 为拆点后的总状态数（

  5 n 5n

  5

  n ）。

// 预处理倍增矩阵
for (int d = 1; (1 << d) <= maxDay; d++) {
    for (int i = 0; i < nSize; i++)
        for (int j = 0; j < nSize; j++)
            for (int k = 0; k < nSize; k++)
                f[d][i][j] = max(f[d][i][j], f[d-1][i][k] + f[d-1][k][j]);
}

3. 时间轴分段处理

• 步骤 ：

  (1) 按美食节时间排序，将总时间分割为多个区间。

  (2) 对每个区间应用倍增法快速计算状态转移。

  (3) 在美食节时间点检查是否可达对应城市，更新愉悦值。

// 处理每个时间段
for (每个美食节时间段) {
    getSum(时间间隔); // 应用倍增矩阵
    if (可达美食节城市) ans[城市] += 额外愉悦值;
}

复杂度分析

• 预处理阶段 ：

  O ( l o g D × ( 5 n ) 3 ) O(log D \times (5n)^3)

  O

  (

  l

  o

  g

  D

  ×

  (

  5

  n

  )

  3

  ) ，

  D D

  D 为最大时间间隔。

• 查询阶段 ：

  O ( k × l o g T × ( 5 n ) 2 ) O(k \times log T \times (5n)^2)

  O

  (

  k

  ×

  l

  o

  g

  T

  ×

  (

  5

  n

  )

  2

  ) ，

  k k

  k 为美食节次数。

• 总体复杂度 ：约

  O ( 1 0 7 ) O(10^7)

  O

  (

  1

  0

  7

  ) 量级，可处理题目最大数据规模

参考代码

#include <bits/stdc++.h>
#define ll long long

#define notDot -1
const int N = 256; // 50*5 每个点分裂成 5 个出来，最多 50 * 5个

ll f[30][N][N]; // f[d][i][j] 从点 i 到点 j 经过 2^d 天后得到的最大权值和
struct node     // 美食街的数据结构
{
    int day, city, happy;
    bool operator<(const node &A) const
    {
        return day < A.day; // 按照美食节的时间进行排序
    };
} food[N];
ll ans[N];    // 记录答案的数组，经过若干天后抵达 i 结点的权值
int happy[N]; // 抵达 i 点的权值
int n, nSize; // nSize=5n

/* 另外经过 day 天，抵达各个节点的最大权值 */
void getSum(int day)
{
    if (day == 0)
        return;                     // 如果是0天，没必要处理
    ll tmp[N];                      // 临时数组
    int k = 1, p = 0;               // 2^p=k
    for (int i = 0; i < nSize; i++) // 初始化无法到达的情况
        tmp[i] = notDot;
    while (k * 2 <= day) // 求出 ⌊ 2^p=k && k<=day ⌋ 的 p 和 k
        p++, k <<= 1;
    for (int i = 0; i < nSize; i++)
        for (int j = 0; j < nSize; j++)
            /* 如果点 i （起始节点）可以抵达，且 i->j 可以抵达 */
            if (ans[i] >= 0 && f[p][i][j] >= 0)
                tmp[j] = std::max(tmp[j], ans[i] + f[p][i][j]); // 经过 2^p 天后的贡献
    for (int i = 0; i < nSize; i++)                             // 复制到 ans
        ans[i] = tmp[i];
    if (day - k > 0)     // 还有天数未计算（不是2^p整数天）
        getSum(day - k); // 递归计算剩余问题
}

int main()
{
    int m, fCount, day;
    std::ios::sync_with_stdio(false), std::cin.tie(nullptr);
    std::cin >> n >> m >> day >> fCount;
    nSize = n * 5;
    for (int i = 0; i < nSize; i++)
    {
        ans[i] = notDot; // 无法可达
        for (int j = 0; j < nSize; j++)
            if (i - 1 == j && i / 5 == j / 5)
                f[0][i][j] = 0; // i 点经过 2^0 天抵达 j 点 边费为0
            else
                f[0][i][j] = notDot; // 其余情况无法直接到达
    }

    // 初始化
    ans[0] = 0; // 初始化站在节点 1，对应五倍扩展后的 0 节点
    for (int i = 0; i < n; i++)
    {
        std::cin >> happy[i];
        f[0][i * 5 + 1][i * 5] = happy[i]; // 到达点 i 的权值/愉悦值
    }

    // 根据美食节，建边
    for (int i = 0, u, v, w; i < m; i++)
    {
        std::cin >> u >> v >> w;
        int newU = u * 5 - 5, newV = v * 5 - 5 + w - 1; // 扩展后，u 点和 v 点 实际抵达的结点位置
        /* u 点到 v 点，如果是1天，则贡献直接为 v 点本身，否则需要再走 w-1 天才可抵达v点，边费为 0  */
        f[0][newU][newV] = (w == 1 ? happy[v - 1] : 0);
    }

    for (int i = 0; i < fCount; i++) // 美食节（ 举行天数、举行的城市、额外的愉悦值 ）
        std::cin >> food[i].day >> food[i].city >> food[i].happy;

    std::sort(food, food + fCount); // 按照美食节的时间进行排序
    int maxLine = 0;
    if (fCount == 0) // 没有美食节，则最大时间间隔就是总的旅游时间
        maxLine = day;
    else
    {
        maxLine = food[0].day; // 注意初始化，不能为 0，测试点为 80pts，少计算一个第一天的时间段
        // 对总时间用每个美食节进行分割，获取最长时间段
        for (int i = 0; i < fCount - 1; i++)
            maxLine = std::max(maxLine, food[i + 1].day - food[i].day);
        // 还要回到起点，看看旅行总天数 - 最后一个美食节的天数是否可以为更长
        maxLine = std::max(maxLine, day - food[fCount - 1].day);
    }

    // 递推倍增求 st 表，状态转移
    for (int d = 1; (1 << d) <= maxLine; d++)
    {
        for (int i = 0; i < nSize; i++)
            for (int j = 0; j < nSize; j++)
            {
                f[d][i][j] = notDot; // 初始化不可达
                for (int k = 0; k < nSize; k++)
                    if (f[d - 1][i][k] >= 0 && f[d - 1][k][j] >= 0) // (i->k) + (k->j) = (i->j), a^d = a^(d-1) + a(d-1);
                        f[d][i][j] = std::max(f[d][i][j], f[d - 1][i][k] + f[d - 1][k][j]);
            }
    }
    int nday = 0;
    for (int i = 0; i < fCount; i++) // 按照每一个美食节的时间段进行倍增、递推
    {
        getSum(food[i].day - nday);
        nday = food[i].day;
        int ed = food[i].city * 5 - 5;
        if (ans[ed] > notDot) // 如果美食节当天可以抵达城市，则增加额外的权值
            ans[ed] += food[i].happy;
    }

    getSum(day - nday);   // 总旅行时间 - 最后一个美食节的时间
    if (ans[0] == notDot) // 如果不能回到起点，则输出 -1，否则可以
        std::cout << notDot << "\n";
    else
        std::cout << ans[0] + happy[0] << "\n"; // 要把初始结点的权值也加上，表示可以回到起点
    return 0;
}

➪ 时间复杂度：主导项：

O ( l o g D × n 3 ) O(log D \times n^3)

O

(

l

o

g

D

×

n

3

) ，下面为详细的分析。

1. 预处理倍增数组（ f[d][i][j] 数组）

   • 循环结构：外层循环

     d d

     d 的迭代次数为

     O ( l o g D ) O(log D)

     O

     (

     l

     o

     g

     D

     ) ，

     D D

     D 是最大时间间隔（例如总天数 day ）。

     内层三重循环

     ( i , j , k ) (i,j,k)

     (

     i

     ,

     j

     ,

     k

     ) 的范围都是

     O ( n ) O(n)

     O

     (

     n

     ) （实际为

     5 n 5n

     5

     n ，但常数可以忽略）。

2. 递归处理时间段（ getSum 函数）

   • 递归次数：对于每个时间段进行二进制拆分，最多处理

     l o g D a y logDay

     l

     o

     g

     D

     a

     y 次。

     共需处理

     O ( f C o u n t + 1 ) O(fCount + 1)

     O

     (

     f

     C

     o

     u

     n

     t

 1

 )
 个时间段（每个美食节分割一次 + 最后剩余天数）。

• 单次处理：m诶次分解需便利所有节点对

  ( i , j ) (i,j)

  (

  i

  ,

  j

  ) ，复杂度

  O ( n 2 ) O(n^2)

  O

  (

  n

  2

  ) 。

• 总复杂度：

  O ( f C o u n t + 1 ) × l o g   d a y × n 2 ) O(fCount + 1) \times log \ day \times n^2)

  O

  (

  f

  C

  o

  u

  n

  t

 1

 )



 ×





 l

 o

 g



 d

 a

 y



 ×






 n









 2

 )
 ，当

 f
 C
 o
 u
 n
 t
 fCount





 f

 C

 o

 u

 n

 t
 较小时可以忽略，较大时可能接近

 O
 (
 l
 o
 g
  
 d
 a
 y
 ×
 n
 3
 )
 O(log \ day \times n^3)





 O

 (

 l

 o

 g



 d

 a

 y



 ×






 n









 3

 )
 。

总结

本题通过 拆点建模 将复杂的时间转移转化为状态转移，结合 倍增法 高效处理大规模天数问题，并巧妙利用事件分割优化计算路径。该解法在时间与空间复杂度间取得平衡，是典型的图论与动态规划结合的高级应用。