小麦の売買で得られる最大利益を求めるC++プログラムの解説

問題の概要

n個の都市がm本の道路で結ばれているとします。道路はすべて一方通行であり、出発地から目的地への一方向にのみ移動できます。道路の情報は配列roadsに{出発地, 目的地}という形式で与えられます。

各都市では小麦の売値が異なり、その価格は配列priceに格納されています（i番目の値はi番目の都市での小麦の価格）。旅行者はどの都市でも小麦を購入でき、移動が許可されている範囲であれば任意の都市へ移動して売却することができます。このとき、小麦の売買によって旅行者が得られる最大の利益を求めるのが本問題です。

例えば、入力が n = 5、m = 4、price = {4, 6, 7, 8, 5}、roads = {{1, 2}, {2, 3}, {2, 4}, {4, 5}} である場合、出力は 4 になります。

これは、旅行者が1番目の都市で小麦を4で購入し、4番目の都市で8で売却すると、利益は 8 − 4 = 4 となり、これが達成可能な最大額だからです。

アルゴリズムの手順

この問題は、グラフを隣接リストとして構築し、各都市に到達するまでの「最低購入価格」を順に伝播させていくことで効率的に解けます。手順は以下の通りです。

サイズn×nの2次元配列graphを定義する。
i := 0 から i < m まで、i を1ずつ増やしながら繰り返す：
   x := roads[i] の1番目の値
   y := roads[i] の2番目の値
   x と y をそれぞれ1減らす（0始まりのインデックスに変換）
   graph[x] の末尾に y を挿入する
サイズnの配列tpを十分大きな値（正の無限大相当）で初期化する。
i := 0 から i < n まで、i を1ずつ増やしながら繰り返す：
   graph[i] 内の各値 u について：
      tp[u] := {tp[u], tp[i], price[i]} の最小値
res := 負の無限大
i := 0 から i < n まで、i を1ずつ増やしながら繰り返す：
   res := res と (price[i] - tp[i]) の最大値
res を返す

アルゴリズムのポイント

tp[i] は「都市iに到達するまでの経路上で小麦を購入できる最低価格」を表します。道路を出発側の都市から順に処理することで、目的地における最低購入価格が更新されていきます。最後に、各都市ごとの「売却価格 − 最低購入価格」の最大値を取れば、それが答えとなります。

C++による実装例

理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;

int solve(int n, int m, vector<int> price, vector<pair<int, int>> roads){
   vector<vector<int>> graph(n);
   for(int i = 0; i < m; i++){
      int x = roads[i].first;
      int y = roads[i].second;
      x--, y--;
      graph[x].push_back(y);
   }
   vector<int> tp(n, INT_MAX);
   for(int i = 0; i < n; i++){
      for(int u : graph[i]){
         tp[u] = min({tp[u], tp[i], price[i]});
      }
   }
   int res = INT_MIN;
   for(int i = 0; i < n; i++){
      res = max(res, price[i] - tp[i]);
   }
   return res;
}

int main() {
   int n = 5, m = 4;
   vector<int> price = {4, 6, 7, 8, 5};
   vector<pair<int, int>> roads = {{1, 2}, {2, 3}, {2, 4}, {4, 5}};
   cout << solve(n, m, price, roads);
   return 0;
}

なお、浮動小数点数のINFINITYをintにキャストするのは未定義動作となるため、上記のコードでは初期化にINT_MAX、答えの初期値にはINT_MINを使用しています。これにより、どの環境でも正しく動作します。

入力

5, 4, {4, 6, 7, 8, 5}, {{1, 2}, {2, 3}, {2, 4}, {4, 5}}

出力

4