मान लीजिए, एक भारित, अप्रत्यक्ष ग्राफ है जिसमें n कोने और m किनारे हैं। ग्राफ़ के स्कोर को ग्राफ़ में सभी किनारों के वज़न के योग के रूप में परिभाषित किया गया है। किनारे के वजन नकारात्मक हो सकते हैं, और यदि उन्हें हटा दिया जाता है तो ग्राफ का स्कोर बढ़ जाता है। हमें क्या करना है, हमें ग्राफ को कनेक्ट रखते हुए ग्राफ से किनारों को हटाकर ग्राफ के स्कोर को न्यूनतम बनाना है। हमें कम किए जा सकने वाले स्कोर की अधिकतम राशि का पता लगाना होगा।
ग्राफ़ एक सरणी 'किनारों' में दिया गया है, जहां प्रत्येक तत्व {वजन, {vertex1, vertex2}} के रूप में है।
इसलिए, यदि इनपुट n =5, m =6, किनारों ={{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
Define an array par of size: 100.
Define an array dim of size: 100.
Define a function make(), this will take v,
par[v] := v
dim[v] := 1
Define a function find(), this will take v,
if par[v] is same as v, then:
return v
return par[v] = find(par[v])
Define a function unify(), this will take a, b,
a := find(a)
b := find(b)
if a is not equal to b, then:
(decrease cnum by 1)
if dim[a] > dim[b], then:
swap values of (a, b)
par[a] := b
dim[b] := dim[b] + dim[a]
cnum := n
sort the array edges based on edge weights
for initialize i := 1, when i <= n, update (increase i by 1), do:
make(i)
res := 0
for each edge in edges, do:
a := first vertex of edge
b := second vertex of edge
weight := weight of edge
if find(a) is same as find(b), then:
if weight >= 0, then:
res := res + 1 * weight
Ignore following part, skip to the next iteration
if cnum is same as 1, then:
if weight >= 0, then:
res := res + 1 * weight
Otherwise
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