समस्या
ऐसे अविनिर्दिष्ट लिंक चुनें ताकि प्रत्येक शीर्षक (vertex) अन्य सभी शीर्षकों तक पहुँच सके, और कुल लागत न्यूनतम हो। कोई भी लिंक दोनों दिशाओं में इस्तेमाल किया जा सकता है। यदि उपलब्ध लिंक पूरे नेटवर्क को नहीं जोड़ सकते, तो −1 लौटाएँ। आपको चुने गए लिंक लौटाने की आवश्यकता नहीं है।
minimum_network_connection_cost(vertices, links) को लागू करें।
इनपुट
vertices: नेटवर्क में शीर्षकों (vertices) की संख्या।
links: उपलब्ध लिंक [u, v, cost] के रूप में।
आउटपुट
न्यूनतम कुल लागत लौटाएँ, यदि असंभव हो तो −1 लौटाएँ, या एक-शीर्षक नेटवर्क के लिए 0 लौटाएँ।
सीमाएँ
1 ≤ vertices ≤ 100,000। 0…200,000 लिंक; एंडपॉइंट्स 1…vertices में विशिष्ट शीर्षक हैं। लागत 1…1,000,000,000 के बीच है। समान एंडपॉइंट्स के लिए एक से अधिक लिंक (parallel links) की अनुमति है। कुल मान signed 64-bit में समा जाता है।
उदाहरण
इनपुट:
links = [
[1, 2, 4],
[2, 3, 2],
[1, 3, 7]
]
vertices = 3
अपेक्षित आउटपुट:
expected = 6इनपुट:
std::vector<std::vector<long long>> links = {
{1, 2, 4},
{2, 3, 2},
{1, 3, 7}
};
long long vertices = 3;
अपेक्षित आउटपुट:
long long expected = 6;इनपुट:
long[][] links = new long[][] {
new long[] {1, 2, 4},
new long[] {2, 3, 2},
new long[] {1, 3, 7}
};
long vertices = 3;
अपेक्षित आउटपुट:
long expected = 6;व्याख्या
सभी तीन शीर्षकों को जोड़ने के लिए लागत 4 और 2 वाले लिंक चुनें। इनकी कुल लागत 6 है; लागत 7 वाला लिंक आवश्यक नहीं है।
इनपुट:
links = [
[1, 2, 4]
]
vertices = 3
अपेक्षित आउटपुट:
expected = -1इनपुट:
std::vector<std::vector<long long>> links = {
{1, 2, 4}
};
long long vertices = 3;
अपेक्षित आउटपुट:
long long expected = -1;इनपुट:
long[][] links = new long[][] {
new long[] {1, 2, 4}
};
long vertices = 3;
अपेक्षित आउटपुट:
long expected = -1;व्याख्या
शीर्षक 3 का कोई कनेक्शन नहीं है। कोई भी चयन पूरे नेटवर्क को नहीं जोड़ सकता।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
तुम्हें links का ऐसा सबसे सस्ता set चाहिए जो फिर भी हर vertex को connected रखे, इसलिए spanning tree सोचो।
संकेत 2
Greedily सबसे सस्ता ऐसा link जोड़ो जो cycle न बनाए, या union-find structure से components बढ़ाओ।
संकेत 3
अगर vertices minus one से कम usable links graph को connect करें, तो answer impossible है।
अपेक्षित जटिलता
समय O(links log links), अतिरिक्त स्थान O(vertices + links)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।