Рассмотрим случай с двумя роботами. Понятно, что роботу с маленьким баком выгодно израсходовать 1/3 часть топлива, на еще 1/3 часть вернуться в начало, а оставшуюся 1/3 отдать второму роботу.

Если роботов 3, то первый отдает второму 1/3 топлива, как в первом случае, а далее аналогично рассматриваем второго робота и третьего. Ну и т.д.

В точке Х у тебя два ограничения — ты не можешь отдать больше Х топлива (потому что у напарника нету места, чтобы принять больше) и не можешь отдать больше ((Volume - X) - X), потому что тогда тебе самому не хватит на дорогу назад.

Это как раз две прямые, твое решение — нижняя огибающая этого набора, максимум будет в точке пересечения.

Volume - 2 * X = X — отсюда X = Volume / 3.

Так что "магические решения" прямо из пересечения линий и выходят.

Выкинем все вершины недостижимые из начала, и из которых недостижим конец. Добавим к каждому ребру обратное бесконечное ребро. Найдём maxflow.

Я сдал в практис руме такое:

В начале сожмем граф по компонентам сильной связности. Если вершины 0 и N — 1 находятся в одной компоненте, то ответ -1. Дальше выбросим все ребра, оба конца которых лежат в одной компоненте. Еще выбросим все вершины, которые не лежат ни на одном пути из старта в финиш.

Теперь если бы не было ограничения на то, что на каждом пути должен быть ровно один чекпоинт, то задача была бы эквивалентна поиску минимального разреза в графе. Сведем нашу задачу к минимальному разрезу следующим образом. Пусть у нас есть ребро a -> b, тогда добавим ребра вида x -> b и a -> y пропускной способности +inf для всех x, которые достижимы из b и для всех y из которых достижима a. Тогда как раз если ребро a -> b попадет в разрез, то никакое другое ребро на пути содержащем a -> b в разрез уже попасть не сможет. EDIT: исходя из комментария выше вместо всех этих махинаций с дополнительными ребрами можно было просто добавить ребро b -> a пропускной способности +inf, обоснование почему это правильно останется примерно таким же.

Если в итоге поток вышел бесконечный, то ответ -1, иначе ответ — величина потока.

I did it this way.

1. Let's find all strongly connected components. If the start and the end vertex are in the same component, the answer is -1.

2. Now we can build a graph where the vertices are strongly connected components and there are all edges from the original graph(except those that lie inside the same component, of course).

3. If there wasn't an additional condition that we can block only one edge on each path, we could have just found the minimum cut in the graph. But we can adjust the graph in such a way that this condition is satisfied. That is, for each pair of edges (A -> B) and (X -> Y), we should add an edge from X to B with cost = INF if and only if A is reachable from the start vertex, the end vertex is reachable from Y and X is reachable from B.

4. The minimum cut(or the maximum flow) in this graph is the answer(if it is < INF, otherwise the answer is -1).

You can't block any edge of a SCC (because cycles), so join all SCCs into a single vertex, and add costs for every edge between SCCs to get new costs.

Now we still have to enforce "can't go through two blocks" condition. To do this, for every edge in the forward direction, make an edge in the reverse direction with infinite capacity.

And please remember to delete all SCCs that aren't part of any 0 to N-1 path before the mincut, otherwise the troll test will hunt you at night.

can you provide the explanation for 2nd problem?, please

The amount of fuel a robot can contain is limited by its capacity

Sort the robots by their capacity in increasing order , then apply this dp:

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cost[i]] / 3 + cap[i])

then the final answer is max(dp[n - 1][i]) / 2

Betlista wrote a short editorial for Div 2 here. You can see a more detailed discussion for the 1000 problem in the comments.