Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

दिए गए ग्राफ में q क्वेरी के लिए सबसे छोटे लागत पथ को ढूंढने के लिए C++ प्रोग्राम


मान लीजिए, हमें एक ग्राफ दिया गया है जिसमें n शीर्ष हैं और यह न्यूनतम रूप से जुड़ा हुआ है। किनारे हमें एक ऐरे में दिए गए हैं जहां किनारे {स्रोत, गंतव्य, वजन} प्रारूप में दिए गए हैं। अब, हमें q संख्या के क्वेरी दिए गए हैं जहां प्रत्येक क्वेरी {स्रोत, गंतव्य} प्रारूप में है। हमें शीर्ष k के माध्यम से स्रोत से गंतव्य तक सबसे छोटे लागत पथ को ढूंढना है। हम प्रत्येक क्वेरी के लिए पथ की लागत प्रिंट करते हैं।

उदाहरण के लिए, यदि इनपुट n = 6, q = 3, k = 1, edges = {{1, 2, 2}, {1, 3, 4}, {3, 4, 2}, {3, 5, 3}, {5, 6, 2}}, queries = {{1, 4}, {2, 6}, {2, 5}} है, तो आउटपुट 6 11 9 होगा।

चरण

इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:

आकार n * n के युग्मों का एक 2D ऐरे graph परिभाषित करें आकार n का एक ऐरे pathTotal परिभाषित करें एक फ़ंक्शन dfs() परिभाषित करें, जो a, b लेता है, graph[a] के प्रत्येक मान i के लिए: यदि i का पहला मान, b के बराबर है, तो: अगले पुनरावृत्ति पर जाएं pathTotal[i का पहला मान] := pathTotal[a] + i का दूसरा मान dfs(i का पहला मान, a) i := 0 से n - 2 तक, करें: a := edges[i] का पहला मान b := edges[i] का दूसरा मान c := edges[i] का तीसरा मान a और b को 1 से घटाएं युग्म (b, c) को graph[a] के अंत में डालें युग्म (a, c) को graph[b] के अंत में डालें k को 1 से घटाएं dfs(k, k) i := 0 से q-1 तक, करें: x := queries[i] का पहला मान y := queries[i] का दूसरा मान x और y को 1 से घटाएं print(pathTotal[x] + pathTotal[y])

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

#include <bits/stdc++.h> using namespace std; vector<vector<pair<int,int>>> graph; vector<int> pathTotal; int k; void dfs(int a, int b){    for(auto i : graph.at(a)){       if(i.first == b) continue;       pathTotal.at(i.first) = pathTotal.at(a) + i.second;       dfs(i.first,a);    } } void solve(int n, int q, vector<tuple<int, int, int>> edges, vector<pair<int, int>> queries){    int a, b, c, x, y;    graph.resize(n);    pathTotal.resize(n);    for(int i = 0; i < n - 1; i++){       a = get<0> (edges[i]);       b = get<1> (edges[i]);       c = get<2> (edges[i]);       a--, b--;       graph.at(a).push_back(make_pair(b, c));       graph.at(b).push_back(make_pair(a, c));    }    k--;    dfs(k, k);    for(int i = 0; i < q; i++){       x = queries[i].first;       y = queries[i].second;       x--, y--;       cout << pathTotal.at(x) + pathTotal.at(y) << endl;    } } int main() {    int n = 6, q = 3;    k = 1;    vector<tuple<int, int, int>> edges = {{1, 2, 2}, {1, 3, 4}, {3, 4, 2}, {3, 5, 3}, {5, 6, 2}}; vector<pair<int, int>> queries = {{1, 4}, {2, 6}, {2, 5}}; solve(n, q, edges, queries); return 0; }

इनपुट

6, 3, 1, {{1, 2, 2}, {1, 3, 4}, {3, 4, 2}, {3, 5, 3}, {5, 6, 2}}, {{1, 4}, {2, 6}, {2, 5}} 

आउटपुट

6 11 9

  1. ग्राफ में सुपर वर्टेक्स खोजने का C++ प्रोग्राम ग्राफ में सुपर वर्टेक्स खोजने का C++ प्रोग्राम

    मान लीजिए n वर्टेक्स वाला एक ग्राफ दिया गया है। वर्टेक्स 1 से n तक संख्याबद्ध हैं और edges सरणी में दी गई एज्स से जुड़े हैं। प्रत्येक वर्टेक्स का एक x मान है जो 1 से n के बीच होता है, यह values सरणी में दिया गया है। हमें ग्राफ में सुपर वर्टेक्स खोजने हैं। एक वर्टेक्स i को सुपर वर्टेक्स कहा जाता है

  1. दिए गए ग्राफ में ब्रिज एज की संख्या ज्ञात करने का C++ प्रोग्राम दिए गए ग्राफ में ब्रिज एज की संख्या ज्ञात करने का C++ प्रोग्राम

    मान लीजिए n वर्टेक्स और m एज वाला एक अनभारित, निदेश रहित ग्राफ दिया गया है। ग्राफ में एक ब्रिज एज वह एज है जिसे हटाने से ग्राफ असंबद्ध हो जाता है। हमें दिए गए ग्राफ में ऐसी एज की संख्या ज्ञात करनी है। ग्राफ में समानांतर एज या सेल्फ-लूप नहीं हैं। उदाहरण के लिए, यदि इनपुट है n = 5, m = 6, edges = {{1

  1. ग्राफ से घटाए जा सकने वाले अधिकतम स्कोर की मात्रा ज्ञात करने का C++ प्रोग्राम ग्राफ से घटाए जा सकने वाले अधिकतम स्कोर की मात्रा ज्ञात करने का C++ प्रोग्राम

    मान लीजिए n वर्टेक्स और m एज वाला एक भारित, निदेश रहित ग्राफ दिया गया है। ग्राफ का स्कोर ग्राफ में सभी एज भारों का योग है। एज भार ऋणात्मक हो सकते हैं, और यदि उन्हें हटा दिया जाए तो ग्राफ का स्कोर बढ़ जाता है। हमें ग्राफ को संबद्ध रखते हुए एज हटाकर ग्राफ के स्कोर को न्यूनतम करना है। हमें घटाए जा सकन