Dada una array arr[] (indexación basada en 1) que consiste en N enteros positivos tales que arr[i] denota la cantidad de la i -ésima persona . También se proporcionan dos arrays 2D , digamos amigos [] [2] y grupos [] [2] , de modo que cada par amigos [i] [0] y amigos [i] [1] son amigos y forman grupos. Cada par de grupos[i][0] y grupos[i][0] indica que los amigos que contienen grupos[i][0] y grupos[i][1] pueden ser amigos entre ellos.
La tarea es encontrar el dinero máximo que se puede recaudar entre ellos sobre la base de las siguientes condiciones:
- Si A y B son amigos y B y C son amigos, entonces A y C son amigos.
- Si puede haber una amistad entre un grupo de personas que tienen A y un grupo de personas que tienen B y si puede haber una amistad entre un grupo de B y un grupo de C entonces hay una amistad entre un grupo de A y un grupo de c _
- Un grupo de amigos forma los grupos.
Ejemplos:
Entrada: arr[] = {5, 2, 3, 6, 1, 9, 8}, amigos[][] = {{1, 2}, {2, 3}, {4, 5}, {6, 7}}, grupos[][] = {{1, 4}, {1, 6}}
Salida: 27
Explicación:
Costo total en el grupo 1 = 5 + 2 + 3 = 10.
Costo total en el grupo 2 = 6 + 1 = 7.
Costo total en el grupo 3 = 9 + 8 = 17.
Como el grupo 1 puede pedir dinero prestado entre ambos, el grupo 2 y grupo 3. Por lo tanto, el dinero máximo recaudado es 10 + 17 = 27.Entrada: arr[] = {1, 2, 3, 4, 5, 6, 7}, amigos[][] = {{1, 2}, {2, 3}, {4, 5}, {6, 7}}, grupos[][] = {{1, 4}, {1, 6}}
Salida: 19
Planteamiento: El problema dado se puede resolver formando un grupo de amigos y hallando la cantidad de dinero que cada grupo puede tener. La idea es usar Disjoint Set Union haciendo que uno de los miembros del grupo sea padre. Siga los pasos a continuación para resolver el problema:
- Mientras forma el grupo, agregue la cantidad de cada grupo de amigos y almacene esta cantidad con el padre de este grupo.
- Agregue un borde entre diferentes grupos donde dos vértices de un borde muestren que estos dos grupos pueden ser amigos entre sí.
- Agregue un borde entre los miembros principales del grupo.
- Dado que el padre almacena la cantidad de dinero que tiene el grupo correspondiente, entonces el problema se reduce a encontrar la ruta de suma máxima desde el Node hasta la hoja donde cada Node en la ruta representa la cantidad de dinero que tiene el grupo.
- Después de completar los pasos anteriores, imprima el valor de la cantidad máxima que se puede cobrar.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
#define N 100001
int n;
int amt[N];
long long dp[N], c[N];
int parent[N];
long long sz[N];
vector<int> v[N];
// Function to find the parent of each
// node in the graph
int find(int i)
{
// If the parent is the same node
// itself
if (parent[i] == i)
return i;
// Recursively find the parent
return parent[i] = find(parent[i]);
}
// Function to merge the friends of
// each groups
void Union(int a, int b)
{
// Find the parents of a and b
int p1 = find(a);
int p2 = find(b);
// If the parents are the same
// then return
if (p1 == p2)
return;
// If the size of the parent p1
// is less than the p2, then
// swap the parents p1 and p2
if (sz[p1] < sz[p2]) {
swap(p1, p2);
}
parent[p2] = p1;
sz[p1] += sz[p2];
// Money in the group of p2 is
// added to the p1 and p2 is
// now the member of p1
c[p1] += c[p2];
// p2 is now the member of p1
c[p2] = 0;
}
// Function to calculate the maximum
// amount collected among friends
void dfs(int src, int par)
{
dp[src] = c[src];
long long mx = 0;
// Traverse the adjacency list
// of the src node
for (auto x : v[src]) {
if (x == par)
continue;
dfs(x, src);
// Calculate the maximum
// amount of the group
mx = max(mx, dp[x]);
}
// Adding the max amount of money
// with the current group
dp[src] += mx;
}
// Function to find the maximum money
// collected among friends
void maximumMoney(
int n, int amt[],
vector<pair<int, int> > friends,
vector<pair<int, int> > groups)
{
// Iterate over the range [1, N]
for (int i = 1; i <= n; i++) {
// Initialize the parent and
// the size of each node i
parent[i] = i;
sz[i] = 1;
c[i] = amt[i - 1];
}
int p = friends.size();
// Merging friends into groups
for (int i = 0; i < p; ++i) {
// Perform the union operation
Union(friends[i].first,
friends[i].second);
}
int m = groups.size();
// Finding the parent of group
// in which member is present
for (int i = 0; i < m; ++i) {
// Find the parent p1 and p2
int p1 = find(groups[i].first);
int p2 = find(groups[i].second);
// p1 and p2 are not in same
// group then add an edge
if (p1 != p2) {
// These two groups can be
// made friends. Hence,
// adding an edge
v[p1].push_back(p2);
v[p2].push_back(p1);
}
}
// Starting dfs from node which
// is the parent of group in
// which 1 is present
dfs(find(1), 0);
long long ans = 0;
// Ans is the maximum money
// collected by each group
for (int i = 1; i <= n; i++) {
ans = max(ans, dp[find(i)]);
}
// Print the answer
cout << ans << endl;
}
// Driver Code
signed main()
{
int amt[] = { 5, 2, 3, 6,
1, 9, 8 };
n = sizeof(amt) / sizeof(amt[0]);
vector<pair<int, int> > friends
= { { 1, 2 }, { 2, 3 }, { 4, 5 }, { 6, 7 } };
vector<pair<int, int> > groups
= { { 1, 4 }, { 1, 6 } };
maximumMoney(n, amt, friends, groups);
return 0;
}
Python3
# Python3 program for the above approach N = 100001 amt = [0] * N dp = [0] * N c = [0] * N parent = [0] * N sz = [0] * N v = [[] for i in range(N)] # Function to find the parent of each # node in the graph def find(i): # If the parent is the same node # itself if (parent[i] == i): return i parent[i] = find(parent[i]) return parent[i] # Function to merge the friends of # each groups def Union(a, b): # Find the parents of a and b p1 = find(a) p2 = find(b) # If the parents are the same # then return if (p1 == p2): return # If the size of the parent p1 # is less than the p2, then # swap the parents p1 and p2 if (sz[p1] < sz[p2]): temp = p1 p1 = p2 p2 = temp parent[p2] = p1 sz[p1] += sz[p2] # Money in the group of p2 is # added to the p1 and p2 is # now the member of p1 c[p1] += c[p2] # p2 is now the member of p1 c[p2] = 0 # Function to calculate the maximum # amount collected among friends def dfs(src, par): dp[src] = c[src] mx = 0 # Traverse the adjacency list # of the src node for x in v[src]: if (x == par): continue dfs(x, src) # Calculate the maximum # amount of the group mx = max(mx, dp[x]) # Adding the max amount of money # with the current group dp[src] += mx # Function to find the maximum money # collected among friends def maximumMoney(n, amt, friends, groups): # Iterate over the range [1, N] for i in range(1, n + 1): # Initialize the parent and # the size of each node i parent[i] = i sz[i] = 1 c[i] = amt[i - 1] p = len(friends) # Merging friends into groups for i in range(p): # Perform the union operation Union(friends[i][0], friends[i][1]) m = len(groups) # Finding the parent of group # in which member is present for i in range(m): # Find the parent p1 and p2 p1 = find(groups[i][0]) p2 = find(groups[i][1]) # p1 and p2 are not in same # group then add an edge if (p1 != p2): # These two groups can be # made friends. Hence, # adding an edge v[p1].append(p2) v[p2].append(p1) # Starting dfs from node which # is the parent of group in # which 1 is present dfs(find(1), 0) ans = 0 # Ans is the maximum money # collected by each group for i in range(1, n + 1): ans = max(ans, dp[find(i)]) # Print the answer print(ans) # Driver Code amt = [ 5, 2, 3, 6, 1, 9, 8 ] n = len(amt) friends = [ [ 1, 2 ], [ 2, 3 ], [ 4, 5 ], [ 6, 7 ] ] groups = [ [ 1, 4 ], [ 1, 6 ] ] maximumMoney(n, amt, friends, groups) # This code is contributed by _saurabh_jaiswal
Javascript
<script>
// JavaScript program for the above approach
let N = 100001
let n;
let amt = new Array(N);
let dp = new Array(N), c = new Array(N);
let parent = new Array(N);
let sz = new Array(N);
let v = new Array(N).fill(0).map(() => []);
// Function to find the parent of each
// node in the graph
function find(i) {
// If the parent is the same node
// itself
if (parent[i] == i)
return i;
// Recursively find the parent
return parent[i] = find(parent[i]);
}
// Function to merge the friends of
// each groups
function Union(a, b) {
// Find the parents of a and b
let p1 = find(a);
let p2 = find(b);
// If the parents are the same
// then return
if (p1 == p2)
return;
// If the size of the parent p1
// is less than the p2, then
// swap the parents p1 and p2
if (sz[p1] < sz[p2]) {
let temp = p1;
p1 = p2;
p2 = temp;
}
parent[p2] = p1;
sz[p1] += sz[p2];
// Money in the group of p2 is
// added to the p1 and p2 is
// now the member of p1
c[p1] += c[p2];
// p2 is now the member of p1
c[p2] = 0;
}
// Function to calculate the maximum
// amount collected among friends
function dfs(src, par) {
dp[src] = c[src];
let mx = 0;
// Traverse the adjacency list
// of the src node
for (let x of v[src]) {
if (x == par)
continue;
dfs(x, src);
// Calculate the maximum
// amount of the group
mx = Math.max(mx, dp[x]);
}
// Adding the max amount of money
// with the current group
dp[src] += mx;
}
// Function to find the maximum money
// collected among friends
function maximumMoney(n, amt, friends, groups) {
// Iterate over the range [1, N]
for (let i = 1; i <= n; i++) {
// Initialize the parent and
// the size of each node i
parent[i] = i;
sz[i] = 1;
c[i] = amt[i - 1];
}
let p = friends.length;
// Merging friends into groups
for (let i = 0; i < p; ++i) {
// Perform the union operation
Union(friends[i][0],
friends[i][1]);
}
let m = groups.length;
// Finding the parent of group
// in which member is present
for (let i = 0; i < m; ++i) {
// Find the parent p1 and p2
let p1 = find(groups[i][0]);
let p2 = find(groups[i][1]);
// p1 and p2 are not in same
// group then add an edge
if (p1 != p2) {
// These two groups can be
// made friends. Hence,
// adding an edge
v[p1].push(p2);
v[p2].push(p1);
}
}
// Starting dfs from node which
// is the parent of group in
// which 1 is present
dfs(find(1), 0);
let ans = 0;
// Ans is the maximum money
// collected by each group
for (let i = 1; i <= n; i++) {
ans = Math.max(ans, dp[find(i)]);
}
// Print the answer
document.write(ans + "<br>");
}
// Driver Code
amt = [5, 2, 3, 6, 1, 9, 8];
n = amt.length;
let friends
= [[1, 2], [2, 3], [4, 5], [6, 7]];
let groups
= [[1, 4], [1, 6]];
maximumMoney(n, amt, friends, groups);
</script>
Producción
27
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por ankitkumar0000333 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA