মান लीজिए, 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।
যদি যাত্রী ১ নম্বর শহর থেকে গম কিনে ৪ নম্বর শহরে বিক্রি করে, তবে মোট লাভ হবে ৪।
সমাধানের ধাপসমূহ
এই সমস্যাটি সমাধান করার জন্য নিচের ধাপগুলো অনুসরণ করব:
nxn আকারের একটি ২D অ্যারে graph সংজ্ঞায়িত করুন। i := 0 দিয়ে আরম্ভ করুন, i < m হলে, (i ১ বাড়িয়ে) করুন: x := roads[i]-র ১ম মান y := roads[i]-র ২য় মান x, y কে ১ কমিয়ে দিন graph[x]-র শেষে y যোগ করুন n আকারের একটি tp অ্যারে সংজ্ঞায়িত করুন, যা ঋণাত্মক অসীম মান দিয়ে আরম্ভ করা আছে। i := 0 দিয়ে আরম্ভ করুন, i < n হলে, (i ১ বাড়িয়ে) করুন: graph[i]-র প্রতিটি মান u জন্য: tp[u] := tp[u], tp[i], price[i] এর ন্যূনতম মান res := ঋণাত্মক অসীম i := 0 দিয়ে আরম্ভ করুন, i < n হলে, (i ১ বাড়িয়ে) করুন: res := 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
