E. Ralph and Mushrooms

Codeforces

IDCF894E

Time2000ms

Memory512MB

Difficulty—

dpgraphs

English · Original

Chinese · Translation

Formal · Original

Ralph is going to collect mushrooms in the Mushroom Forest. There are _m_ directed paths connecting _n_ trees in the Mushroom Forest. On each path grow some mushrooms. When Ralph passes a path, he collects all the mushrooms on the path. The Mushroom Forest has a magical fertile ground where mushrooms grow at a fantastic speed. New mushrooms regrow as soon as Ralph finishes mushroom collection on a path. More specifically, after Ralph passes a path the _i_\-th time, there regrow _i_ mushrooms less than there was before this pass. That is, if there is initially _x_ mushrooms on a path, then Ralph will collect _x_ mushrooms for the first time, _x_ - 1 mushrooms the second time, _x_ - 1 - 2 mushrooms the third time, and so on. However, the number of mushrooms can never be less than 0. For example, let there be 9 mushrooms on a path initially. The number of mushrooms that can be collected from the path is 9, 8, 6 and 3 when Ralph passes by from first to fourth time. From the fifth time and later Ralph can't collect any mushrooms from the path (but still can pass it). Ralph decided to start from the tree _s_. How many mushrooms can he collect using only described paths? ## Input The first line contains two integers _n_ and _m_ (1 ≤ _n_ ≤ 106, 0 ≤ _m_ ≤ 106), representing the number of trees and the number of directed paths in the Mushroom Forest, respectively. Each of the following _m_ lines contains three integers _x_, _y_ and _w_ (1 ≤ _x_, _y_ ≤ _n_, 0 ≤ _w_ ≤ 108), denoting a path that leads from tree _x_ to tree _y_ with _w_ mushrooms initially. There can be paths that lead from a tree to itself, and multiple paths between the same pair of trees. The last line contains a single integer _s_ (1 ≤ _s_ ≤ _n_) — the starting position of Ralph. ## Output Print an integer denoting the maximum number of the mushrooms Ralph can collect during his route. [samples] ## Note In the first sample Ralph can pass three times on the circle and collect 4 + 4 + 3 + 3 + 1 + 1 = 16 mushrooms. After that there will be no mushrooms for Ralph to collect. In the second sample, Ralph can go to tree 3 and collect 8 mushrooms on the path from tree 1 to tree 3.

Ralph 计划在蘑菇森林中采集蘑菇。蘑菇森林中有 #cf_span[m] 条有向路径连接 #cf_span[n] 棵树。每条路径上都生长着一些蘑菇。当 Ralph 经过一条路径时，他会收集该路径上所有的蘑菇。蘑菇森林拥有神奇的肥沃土壤，蘑菇以惊人的速度再生。具体而言，在 Ralph 第 #cf_span[i] 次经过某条路径后，该路径上再生的蘑菇数量比上次经过前少 #cf_span[i] 个。也就是说，如果一条路径初始有 #cf_span[x] 个蘑菇，那么 Ralph 第一次经过时收集 #cf_span[x] 个蘑菇，第二次经过时收集 #cf_span[x - 1] 个蘑菇，第三次经过时收集 #cf_span[x - 1 - 2] 个蘑菇，依此类推。但蘑菇数量永远不会低于 #cf_span[0]。例如，若一条路径初始有 #cf_span[9] 个蘑菇，则 Ralph 第一次到第四次经过时分别可收集 #cf_span[9]、#cf_span[8]、#cf_span[6] 和 #cf_span[3] 个蘑菇。从第五次及以后，Ralph 无法再从该路径上收集任何蘑菇（但仍可经过）。 Ralph 决定从树 #cf_span[s] 出发。他仅通过上述路径最多能收集多少蘑菇？第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 106]，#cf_span[0 ≤ m ≤ 106]），分别表示树的数量和有向路径的数量。接下来的 #cf_span[m] 行每行包含三个整数 #cf_span[x]、#cf_span[y] 和 #cf_span[w]（#cf_span[1 ≤ x, y ≤ n]，#cf_span[0 ≤ w ≤ 108]），表示一条从树 #cf_span[x] 指向树 #cf_span[y] 的路径，初始有 #cf_span[w] 个蘑菇。可能存在从一棵树到自身的路径，以及连接相同两棵树的多条路径。最后一行包含一个整数 #cf_span[s]（#cf_span[1 ≤ s ≤ n]）—— Ralph 的起始位置。请输出一个整数，表示 Ralph 在其路线中最多能收集的蘑菇数量。在第一个样例中，Ralph 可以在环路上经过三次，收集 #cf_span[4 + 4 + 3 + 3 + 1 + 1 = 16] 个蘑菇。之后该路径上将不再有蘑菇可供采集。在第二个样例中，Ralph 可以前往树 #cf_span[3]，并在从树 #cf_span[1] 到树 #cf_span[3] 的路径上收集 #cf_span[8] 个蘑菇。 ## Input 第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 106]，#cf_span[0 ≤ m ≤ 106]），分别表示树的数量和有向路径的数量。接下来的 #cf_span[m] 行每行包含三个整数 #cf_span[x]、#cf_span[y] 和 #cf_span[w]（#cf_span[1 ≤ x, y ≤ n]，#cf_span[0 ≤ w ≤ 108]），表示一条从树 #cf_span[x] 指向树 #cf_span[y] 的路径，初始有 #cf_span[w] 个蘑菇。可能存在从一棵树到自身的路径，以及连接相同两棵树的多条路径。最后一行包含一个整数 #cf_span[s]（#cf_span[1 ≤ s ≤ n]）—— Ralph 的起始位置。 ## Output 请输出一个整数，表示 Ralph 在其路线中最多能收集的蘑菇数量。 [samples] ## Note 在第一个样例中，Ralph 可以在环路上经过三次，收集 #cf_span[4 + 4 + 3 + 3 + 1 + 1 = 16] 个蘑菇。之后该路径上将不再有蘑菇可供采集。在第二个样例中，Ralph 可以前往树 #cf_span[3]，并在从树 #cf_span[1] 到树 #cf_span[3] 的路径上收集 #cf_span[8] 个蘑菇。

Let $ G = (V, E) $ be a directed multigraph with $ |V| = n $ vertices and $ |E| = m $ edges. Each edge $ e = (u, v) \in E $ has an initial mushroom count $ w_e \geq 0 $. For each edge $ e $, if traversed $ k $ times, the total mushrooms collected from $ e $ is: $$ \sum_{i=1}^{k} \max\left(0, w_e - \frac{i(i-1)}{2}\right) $$ Define the function $ f_e(k) = \sum_{i=1}^{k} \max\left(0, w_e - \frac{i(i-1)}{2}\right) $, which gives the total mushrooms collected from edge $ e $ when traversed $ k $ times. Let $ x_e \in \mathbb{Z}_{\geq 0} $ denote the number of times edge $ e $ is traversed. Ralph starts at vertex $ s $. The sequence of traversals must form a walk starting at $ s $, and the flow conservation constraint must hold at every vertex: for each vertex $ v \in V $, $$ \sum_{e \in \text{in}(v)} x_e = \sum_{e \in \text{out}(v)} x_e $$ except for the start vertex $ s $, where: $$ \sum_{e \in \text{out}(s)} x_e = \sum_{e \in \text{in}(s)} x_e + 1 $$ The objective is to maximize the total mushrooms collected: $$ \max \sum_{e \in E} f_e(x_e) $$ subject to the above flow constraints and $ x_e \in \mathbb{Z}_{\geq 0} $ for all $ e \in E $.

Samples

Input #1

Output #1

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "E. Ralph and Mushrooms",
    "description": {
      "content": "Ralph is going to collect mushrooms in the Mushroom Forest. There are _m_ directed paths connecting _n_ trees in the Mushroom Forest. On each path grow some mushrooms. When Ralph passes a path, he co",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF894E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Ralph is going to collect mushrooms in the Mushroom Forest.\n\nThere are _m_ directed paths connecting _n_ trees in the Mushroom Forest. On each path grow some mushrooms. When Ralph passes a path, he co...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Ralph 计划在蘑菇森林中采集蘑菇。\n\n蘑菇森林中有 #cf_span[m] 条有向路径连接 #cf_span[n] 棵树。每条路径上都生长着一些蘑菇。当 Ralph 经过一条路径时，他会收集该路径上所有的蘑菇。蘑菇森林拥有神奇的肥沃土壤，蘑菇以惊人的速度再生。具体而言，在 Ralph 第 #cf_span[i] 次经过某条路径后，该路径上再生的蘑菇数量比上次经过前少 #cf_span[i] 个...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ G = (V, E) $ be a directed multigraph with $ |V| = n $ vertices and $ |E| = m $ edges. Each edge $ e = (u, v) \\in E $ has an initial mushroom count $ w_e \\geq 0 $.\n\nFor each edge $ e $, if trave...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments