밀 판매로 얻을 수 있는 최대 이익을 알아내는 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입니다.

단계

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

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