मान लीजिए, ऐसे कई शहर हैं जो m सड़कों से जुड़े हैं। सड़कें यूनिडायरेक्शनल हैं, सड़कें केवल स्रोत से गंतव्य तक जा सकती हैं, विपरीत नहीं। सड़कों को सरणी 'सड़कों' में प्रारूप {स्रोत, गंतव्य} में दिया गया है। अब शहरों में गेहूं अलग-अलग दामों पर बिकता है। शहरों में गेहूं की कीमत एक सरणी 'कीमत' में दी जाती है, जहां i-th मान i-th शहर में गेहूं की कीमत है। अब, यात्री किसी भी शहर से गेहूं खरीद सकता है और किसी भी शहर में पहुंच सकता है (यदि यह अनुमति है) और इसे बेच सकता है। हमें यह पता लगाना है कि गेहूँ का व्यापार करके यात्री को अधिकतम कितना लाभ प्राप्त हो सकता है।
इसलिए, यदि इनपुट 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