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

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


मान लीजिए 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) हटा दें, तो स्कोर में कुल कमी 4 होगी और ग्राफ संबद्ध रहेगा।

चरण

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

cnum := 0
आकार 100 के सरणी par, dim परिभाषित करें
एक फंक्शन make() परिभाषित करें जो v लेता है:
    par[v] := v
    dim[v] := 1
एक फंक्शन find() परिभाषित करें जो v लेता है:
    यदि par[v] == v, तो v लौटाएँ
    par[v] = find(par[v]) लौटाएँ
एक फंक्शन unify() परिभाषित करें जो a, b लेता है:
    a := find(a)
    b := find(b)
    यदि a != b, तो:
        cnum घटाएँ
        यदि 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 का भार
    यदि find(a) == find(b), तो:
        यदि weight >= 0, तो:
            res := res + weight
        जारी रखें
    यदि cnum == 1, तो:
        यदि weight >= 0, तो:
            res := res + weight
    अन्यथा:
        unify(a, b)
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
  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++ प्रोग्राम: ग्राफ की एज कनेक्टिविटी खोजें

    इस प्रोग्राम में हमें ग्राफ की एज कनेक्टिविटी खोजने की आवश्यकता है। ग्राफ की एज कनेक्टिविटी का अर्थ है कि यह एक ब्रिज है, इसे हटाने पर ग्राफ डिस्कनेक्ट हो जाएगा। डिस्कनेक्टेड अनडायरेक्टेड ग्राफ में ब्रिज को हटाने पर कनेक्टेड कंपोनेंट्स की संख्या बढ़ जाती है। फंक्शन और छद्मकोड: Begin    Fu