মান লিজিয়ে, একটি ভারসাম্যপূর্ণ, অনির্দেশ গ্রাফ আছে যাতে n টি ভেরটেক্স এবং m টি এজ রয়েছে। গ্রাফের স্কোর হলো সব এজের ওজনগুলোর যোগফল। এজের ওজন ঋণাত্মক হতে পারে, এবং এগুলো মুছে ফেললে গ্রাফের স্কোর বাড়ে। আমাদের কাজ হলো গ্রাফটি সংযুক্ত রেখে এজ মুছে ফেলে গ্রাফের স্কোর সর্বনিম্ন করা। আমাদের লক্ষ্য হলো স্কোরে সর্বোচ্চ কত কমতি আনা যায় তা বের করা।
গ্রাফটি 'edges' অ্যারেতে দেওয়া আছে, যেখানে প্রতিটি উপাদান হলো {weight, {vertex1, vertex2}}।
যেমন, ইনপুট হলে n = 5, m = 6, edges = {{2, {1, 2}}, {2, {1, 3}}, {1, {2, 3}}, {3, {2, 4}}, {2, {2, 5}}, {1, {3, 5}}}, তবে আউটপুট হবে 4।
যদি আমরা (1, 2) এবং (2, 5) এজগুলো মুছে ফেলি, তবে স্কোরে মোট ৪ কমানো যায় এবং গ্রাফ সংযুক্ত থাকে।
সমাধানের ধাপসমূহ
এই সমস্যাটি সমাধান করার জন্য নিচের ধাপগুলো অনুসরণ করব:
cnum := 0 par অ্যারে সংজ্ঞায়িত করুন আকার: ১০০। dim অ্যারে সংজ্ঞায়িত করুন আকার: ১০০। make() ফাংশন সংজ্ঞায়িত করুন, যা v গ্রহণ করবে: par[v] := v dim[v] := 1 find() ফাংশন সংজ্ঞায়িত করুন, যা v গ্রহণ করবে: if par[v] == v, তবে: return v return par[v] = find(par[v]) unify() ফাংশন সংজ্ঞায়িত করুন, যা a, b গ্রহণ করবে: a := find(a) b := find(b) if a != b, তবে: (cnum ১ কমিয়ে) if dim[a] > dim[b], তবে: a, b স왪 করুন par[a] := b dim[b] := dim[b] + dim[a] cnum := n edges অ্যারে ওজন অনুযায়ী সোর্ট করুন i := 1 থেকে n পর্যন্ত: make(i) res := 0 edges-র প্রতিটি edge জন্য: a := edge-র ১ম ভেরটেক্স b := edge-র ২য় ভেরটেক্স weight := edge-র ওজন if find(a) == find(b), তবে: if weight >= 0, তবে: res := res + 1 * weight continue if cnum == 1, তবে: if weight >= 0, তবে: res := res + 1 * weight অন্যথায়: unify(a, b) return res
উদাহরণ
নিচের ইমপ্লিমেন্টেশনটি দেখুন আরও ভালো বুঝতে:
#include <bits/stdc++.h> using namespace std; int cnum = 0; int par[100]; int dim[100]; void make(int v){ par[v] = v; dim[v] = 1; } int find(int v){ if(par[v] == v) return v; return par[v] = find(par[v]); } void unify(int a, int b){ a = find(a); b = find(b); if(a != b){ cnum--; if(dim[a] > dim[b]){ swap(a, b); } par[a] = b; dim[b] += dim[a]; } } int solve(int n, int m, vector <pair <int, pair<int,int>>> edges){ cnum = n; sort(edges.begin(), edges.end()); for(int i = 1; i <= n; i++) make(i); int res = 0; for(auto &edge : edges){ int a = edge.second.first; int b = edge.second.second; int weight = edge.first; if(find(a) == find(b)) { if(weight >= 0) res += 1 * weight; continue; } if(cnum == 1){ if(weight >= 0) res += 1 * weight; } else{ unify(a, b); } } return res; } int main() { int n = 5, m = 6; vector <pair<int, pair<int,int>>> edges = {{2, {1, 2}}, {2, {1, 3}}, {1, {2, 3}}, {3, {2, 4}}, {2, {2, 5}}, {1, {3, 5}}}; cout<< solve(n, m, edges); return 0; } ইনপুট
5, 6, {{2, {1, 2}}, {2, {1, 3}}, {1, {2, 3}}, {3, {2, 4}}, {2, {2, 5}}, {1, {3, 5}}} আউটপুট
4
