C++程序,用于找出销售小麦所能获得的最大利润


假设有n个城市,由m条道路连接。道路是单向的,道路只能从起点到终点,反之则不行。道路以数组'roads'的形式给出,格式为{起点,终点}。现在,这些城市里的小麦以不同的价格出售。各个城市的小麦价格在一个数组'price'中给出,其中第i个值是第i个城市的小麦价格。现在,旅行者可以从任何城市购买小麦,并到达任何城市(如果允许)出售。我们必须找出旅行者通过交易小麦所能获得的最大利润。

因此,如果输入类似于n = 5,m = 3,price = {4, 6, 7, 8, 5},roads = {{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

示例

让我们看看以下实现以获得更好的理解:

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

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

输入

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

输出

4

更新于: 2022年3月2日

281 次查看

开启你的 职业生涯

通过完成课程获得认证

立即开始
广告