小麦の販売から達成できる最大の利益を見つけるためのC++プログラム

m本の道路に接続されている都市がn個あるとします。道路は一方向であり、道路は出発地から目的地までしか行くことができず、その逆はできません。道路は、{source、destination}の形式で配列「roads」で指定されます。現在、都市では、小麦はさまざまな価格で販売されています。都市全体の小麦の価格は、配列「価格」で示されます。ここで、i番目の値はi番目の都市の小麦の価格です。現在、旅行者はどの都市からでも小麦を購入でき、（許可されている場合は）どの都市にも到達して販売することができます。旅行者が小麦を取引することで達成できる最大の利益を見つけなければなりません。

したがって、入力がn =5、m =3、価格={4、6、7、8、5}、道路={{1、2}、{2、3}、{2、4}、 {4、5}}の場合、出力は4になります。

旅行者が最初の都市で小麦を購入し、それを4番目の都市で販売した場合、達成された利益の合計額は4になります。

ステップ

これを解決するには、次の手順に従います-

Define one 2D array graph of size nxn.
for initialize i := 0, when i < m, update (increase i by 1), do:
   x := first value of roads[i]
   y := second value of roads[i]
   decrease x, y by 1
   insert y at the end of graph[x]
Define an array tp of size n initialized with value negative infinity.
for initialize i := 0, when i < n, update (increase i by 1), do:
   for each value u in graph[i], do:
      tp[u] := minimum of ({tp[u], tp[i], price[i]})
res := negative infinity
for initialize i := 0, when i < n, update (increase i by 1), do:
   res := maximum of (res and price[i] - tp[i])
return res

例

理解を深めるために、次の実装を見てみましょう-

#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, y;
      x = roads[i].first;
      y = roads[i].second;
      x--, y--;
      graph[x].push_back(y);
   }
   vector<int> tp(n, int(INFINITY));
   for(int i = 0; i < n; i++){
      for(int u : graph[i]){
         tp[u] = min({tp[u], tp[i], price[i]});
      }
   }
   int res = -int(INFINITY);
   for(int i = 0; i < n; i++){
      res = max(res, price[i] - tp[i]);
   }
   return res;
}
int main() {
   int n = 5, m = 3;
   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;
}

入力

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

出力

4