Courses

動的プログラミング

動的グラフプログラミング

Module: 動的グラフプログラミング

Problem

7 /7

エンとキノコ

Theory Click to read/hide

グラフにサイクルが含まれている場合 (トポロジカルな並べ替えがない場合)、次の 2 つのトリックが役に立ちます。

1) ダイナミクスを n 回計算します。ここで、n はグラフ内の頂点の数です (Ford-Bellman アルゴリズムとの類推による)。しかし、これでは漸近線が大きくなり、一般に効率的になることはほとんどありません。

2) グラフの圧縮を構築します。元のグラフの強連結成分ごとに、問題を個別に解決します。凝縮されたグラフは非巡回であり、その場合、頂点値として、強く接続されたコンポーネントの計算値を使用しながら、トポロジカルソートによる標準的なアプローチを使用できます。この方法が主に使われます。

Problem

エンはきのこの森にきのこを採りに行く。

きのこの森には、n本の木をつなぐm本の道があります。きのこはすべての道に成長します。エンが小道を歩くと、その小道にあるキノコをすべて拾います。しかし、きのこの森には、きのこが驚異的な速度で成長するほどの肥沃な土壌があります。エンが道でキノコを採り終えるとすぐに新しいキノコが生えてきます。つまり、En がパスを i 回通過した後、このパスを通過する前よりも i 個のキノコが少なくなります。したがって、パスに最初に x 個のキノコがあった場合、En は 1 回目のパスで x 個のキノコを収集し、2 回目のパスで x - 1 個のキノコを収集し、3 回目のパスで x - 1 - 2 個のキノコを収集する、というようになります。の上。ただし、キノコの数が0未満になることはありません。
たとえば、最初に 9 つのきのこが道に生えたとします。 En が収集するキノコの数は、パス 1 ～ 4 で 9、8、6、および 3 です。 5 回目以降、En はこのパスから何も収集できなくなります (ただし、このパスを歩くことはできます)。

En は tree s から始めることにしました。説明されたパスに沿って移動するだけで収集できるキノコの最大数は?

入力:
最初の行には、2 つの整数 n と m (1 ≤ n ≤ 300000, 0 ≤ m ≤ 300000) — が含まれています。それぞれ、キノコの森の木の数と方向性のある小道の数です。
次の m 行のそれぞれには、3 つの整数 x、y、および w が含まれます (1 ≤ x, y ≤ n, 0 ≤ w ≤ 10⁸) ツリー x からツリー y に至るパスを記述し、最初に w 個のキノコを使用します。 1 本の木から同じ木へと続く道と、同じ 2 本の木を結ぶいくつかの道があります。
最後の行には、単一の整数 s (1 ≤ s ≤ n) — が含まれています。えんのスタート地点。

出力:
単一の整数を出力します —エンが途中で集められるキノコの最大数。

例:
<本体>
説明:
最初の例では、En は円を 3 回周回し、4 + 4 + 3 + 3 + 1 + 1 = 16 個のキノコを収集できます。その後、En が収集するキノコがなくなります。
2 番目の例では、エンは木 3 に行き、木 1 から木 3 への道で 8 つのキノコを選ぶことができます。

time 1500 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking