Chương trình C ++ để tìm ra số lợi nhuận tối đa có thể đạt được từ việc bán lúa mì

Giả sử, có n số thành phố được kết nối với m đường. Những con đường là một chiều, những con đường chỉ có thể đi từ nguồn đến đích chứ không thể ngược lại. Các con đường được cho trong mảng 'đường' ở định dạng {nguồn, đích}. Bây giờ, ở các thành phố, lúa mì được bán với nhiều giá khác nhau. Giá lúa mì ở các thành phố được cho trong một mảng 'giá', trong đó giá trị thứ i là giá lúa mì ở thành phố thứ i. Giờ đây, một khách du lịch có thể mua lúa mì từ bất kỳ thành phố nào và có thể đến bất kỳ thành phố nào (nếu được phép) và bán nó. Chúng tôi phải tìm ra mức lợi nhuận tối đa mà khách du lịch có thể đạt được bằng cách kinh doanh lúa mì.

Vì vậy, nếu đầu vào là n =5, m =3, price ={4, 6, 7, 8, 5}, đường ={{1, 2}, {2, 3}, {2, 4}, {4, 5}}, thì đầu ra sẽ là 4.

Nếu người du lịch mua lúa mì ở thành phố thứ nhất và bán ở thành phố thứ tư, thì tổng số lợi nhuận đạt được là 4.

Các bước

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

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

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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;
}

Đầu vào

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

Đầu ra

4