পাইথনে গ্রাফের সব ভের্টেক্সের মধ্যবর্তী ন্যূনতম খরচের যোগফল বের করার প্রোগ্রাম

মনে করুন একটি ওজনযুক্ত গ্রাফ আছে যার n ভের্টেক্স এবং m এজ। এজগুলোর ওজন ২-এর ঘাত হিসেবে আছে। গ্রাফের যেকোনো ভের্টেক্স থেকে অন্য যেকোনো ভের্টেক্সে যাওয়া যায়, এবং যাত্রার খরচ হবে পথে ব্যবহৃত সকল এজ ওজনের যোগফল। আমাদের প্রতিটি ভের্টেক্স জোড়ার মধ্যবর্তী ন্যূনতম খরচের যোগফল বের করতে হবে।

যেমন, ইনপুট এমন হলে

এবং ভের্টেক্স সংখ্যা (n) = 6 হলে, আউটপুট হবে ২৬৯৬।

সকল দূরত্বের যোগফল ২৬৯৬।

সমাধান পদ্ধতি

এই সমস্যাটি সমাধান করতে নিচের ধাপগুলো অনুসরণ করুন:

par_finder() ফাংশন ডিফাইন করুন। এটি i, par প্যারামিটার নেবে
- যদি par[i] == -1 হয়, তবে
  - i রিটার্ন করুন
- res := par_finder(par[i], par)
- par[i] := res
- res রিটার্ন করুন
helper() ফাংশন ডিফাইন করুন। এটি i, par, w, G, n প্যারামিটার নেবে
- child := 1
- G[i]-এ থাকা প্রতিটি item-এর জন্য
  - যদি item[0] == par হয়, তবে
    - নেক্সট ইটারেশনে যান
  - অন্যথায়,
    - child := child + helper(item[0], i, item[1], G, n)
  - যদি par != -1 হয়, তবে
    - ans := ans + child * (n - child) * (1 << w)
  - child রিটার্ন করুন
G := n + 1 সংখ্যক খালি লিস্ট ধারণকারী একটি লিস্ট
edges := একটি খালি লিস্ট
roads-এ থাকা প্রতিটি item-এর জন্য
- u := item[0], v := item[1], w := item[2]
- (u-1, v-1, w) edges-এ অ্যাপেন্ড করুন
edges-কে এজ ওজন অনুযায়ী সর্ট করুন
par := -1 দিয়ে n + 1 সাইজের একটি লিস্ট
r_edge := একটি খালি লিস্ট
edges-এ থাকা প্রতিটি i-এর জন্য
- যদি par_finder(i[0], par) == par_finder(i[1], par) হয়, তবে
  - নেক্সট ইটারেশনে যান
- অন্যথায়,
  - i কে r_edge-এ অ্যাপেন্ড করুন
  - (i[1], i[2]) কে G[i[0]]-এ এবং (i[0], i[2]) কে G[i[1]]-এ অ্যাপেন্ড করুন
  - par[par_finder(i[0], par)] := par_finder(i[1], par)
ans := 0
helper(0, -1, 0, G, n) কল করুন
ans রিটার্ন করুন

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন আরও ভালো বোঝার জন্য:

def par_finder(i, par) :     if par[i] == -1 :          return i     res = par_finder(par[i], par)     par[i] = res     return res def helper(i, par, w, G, n) :     global ans     child = 1     for item in G[i] :         if item[0] == par :             continue         else :             child += helper(item[0],i,item[1], G, n)     if par != -1 :         ans += child * (n - child) * (1 << w)     return child def solve(n, roads):     global ans     G = [[] for i in range(n + 1)]     edges = []     for item in roads :         u,v,w = map(int, item)         edges.append((u-1, v-1, w))     edges = sorted(edges,key = lambda item : item[2])     par = [-1 for i in range(n + 1)]     r_edge = []     for i in edges :         if par_finder(i[0], par) == par_finder(i[1], par) :             continue         else :             r_edge.append(i)             G[i[0]].append((i[1],i[2]))             G[i[1]].append((i[0],i[2]))             par[par_finder(i[0], par)] = par_finder(i[1], par)     ans = 0           helper(0, -1, 0, G, n)     return ans print(solve(6, [(1,4,8), (2,4,4), (3,4,4), (3,4,2), (5,3,8), (6,3,2)]))

ইনপুট

6, [(1,4,8), (2,4,4), (3,4,4), (3,4,2), (5,3,8), (6,3,2)]