資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究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示例
讓我們看看以下實現以獲得更好的理解：
#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
更新於: 2022年3月2日
281 次檢視
廣告