मान लीजिए 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 होगा।
चरण
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:
आकार n×n का एक 2D सरणी graph परिभाषित करें
i := 0 से प्रारंभ करें, जब i < m, i को 1 से बढ़ाते हुए:
x := roads[i] का पहला मान
y := roads[i] का दूसरा मान
x, y को 1 घटाएँ
y को graph[x] के अंत में डालें
आकार n का एक सरणी tp परिभाषित करें जिसे ऋणात्मक अनंत से आरंभ किया गया हो
i := 0 से प्रारंभ करें, जब i < n, i को 1 से बढ़ाते हुए:
graph[i] में प्रत्येक मान u के लिए:
tp[u] := min({tp[u], tp[i], price[i]}) का न्यूनतम
res := ऋणात्मक अनंत
i := 0 से प्रारंभ करें, जब i < n, i को 1 से बढ़ाते हुए:
res := max(res, price[i] - tp[i])
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
