Maximize the sum of all people’s travel distances
Given a group of N people who hate each other such that each of them lives in a different city. The cities are connected by N-1 roads such that road[i] = {u, v, w} indicates distance between city u and city v is w. The task is to design a travel plan such that two rules should be satisfied:
- All the people should go to one of the other person’s city.
- Two of them never go to the same city.
Maximize the sum of all people’s travel distances in your travel plan. The travel distance of a person is the distance between the city he lives in and the city he travels to. The travelers always choose the shortest path when traveling.
Examples:
Input: N=4, Roads = [[1 2 3], [2 3 2], [4 3 2]]
Output: 18Input: N=6, Roads = [[1 2 3], [2 3 4], [2 4 1], [4 5 8], [5 6 5]]
Output: 62
Maximum Distance Travelled using DFS and Combinatorics
Firstly, we can visualize this problem statement as a TREE where each city act as a vertex of our tree and each road connection act as an edge between vertices.
In order to maximize the total distance travelled we need to maximize the contribution of each and every edge as much as possible let us see how using the below example tree.
Suppose we want to maximize the contribution of edge between node 4 and 5 into our final sum. To do this lets first answer some simple observations:
Question: What are the nodes that are on left side of our edge?
Answer: 1, 2, 3, 4
Question: What are the nodes that are on right side of our edge?
Answer: 5, 6, 7, 8, 9, 10
Question: Is it optimal to move people from left side nodes in such a way that they remain in left side?
Answer: No, imagine we move person at node 1 to node 3, clearly we can observe that the contibution of our requried edge (between node 4 and 5) will be 0 if we do this.
Question: Is it optimal to move people from right side nodes in such a way that they remain in right side?
Answer: No, imagine we move person at node 8 to node 10, clearly we can observe that the contibution of our requried edge (between node 4 and 5) will be 0 if we do this.
Question: What is the best way to move people from one node to another ?
Answer: By answering above questions you would have clearly realized that it is best to move people from left nodes to right nodes and vice versa. This will result in the maximum contribution of our edge i.e. using basic combinatorics:
- Minimum (total left nodes, total right nodes) * edge weight * 2
We multiply this number by left people move to right and right people move to left.
Using this we can compute the maximum contribution of each and every edge and finally return their sum as our maximum distance travelled.
Step-by-step algorithm:
- Create a adjacency weighted tree from the given input.
- We can use a count[] array to keep track of number of childrens for a node, using this we can calculate:
- number of nodes on left of node x = count [x]
- number of nodes on right of node x = total nodes – count [x]
- Call the depth first search to calculate the count array
- Iterate on each edge and add its maximum contribution to the final answer using the below formula:
- Min(count[x], total nodes-count[x]) * edge weight * 2
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> #define ll long long using namespace std; int dfs(vector<vector<pair< int , int > > >& g, vector< int >& vis, vector< int >& count, int n, int vrtx, int & ans) { // mark the current node visited vis[vrtx] = 1; // increment the count of vertex by 1 count[vrtx] = 1; // dfs call on every neighbour of current vertex for ( auto child : g[vrtx]) { int cv = child.first; int wt = child.second; if (!vis[cv]) { count[vrtx] += dfs(g, vis, count, n, cv, ans); // x and y stores the number of vertices on left // and right side of vrtx int x = count[cv]; int y = n - x; // add the contribution of the current wt to the // ans ans += min(x, y) * 2 * wt; } } return count[vrtx]; } // Driver code int main() { // Taking input int N = 4; vector<vector< int > > roads = { { 1, 2, 3 }, { 2, 3, 2 }, { 4, 3, 2 } }; // constructing a bidirectional graph using the given // input vector<vector<pair< int , int > > > g(N + 1); for ( int i = 0; i < N - 1; i++) { int u, v, w; u = roads[i][0]; v = roads[i][1]; w = roads[i][2]; g[u].push_back({ v, w }); g[v].push_back({ u, w }); } // visited array vector< int > vis(N + 1, 0); // count array to keep track of number of vertices on // the left and right side of every vertex vector< int > count(N + 1, 0); // initialize answer to 0 int ans = 0; // dfs call to calculate the result dfs(g, vis, count, N, 1, ans); cout << ans << endl; } |
Java
import java.util.ArrayList; import java.util.List; class Main { static int dfs(List<List<Pair>> g, List<Integer> vis, List<Integer> count, int n, int vrtx, int [] ans) { // mark the current node visited vis.set(vrtx, 1 ); // increment the count of vertex by 1 count.set(vrtx, 1 ); // dfs call on every neighbour of current vertex for (Pair child : g.get(vrtx)) { int cv = child.first; int wt = child.second; if (vis.get(cv) == 0 ) { count.set(vrtx, count.get(vrtx) + dfs(g, vis, count, n, cv, ans)); // x and y stores the number of vertices on left // and right side of vrtx int x = count.get(cv); int y = n - x; // add the contribution of the current wt to the // ans ans[ 0 ] += Math.min(x, y) * 2 * wt; } } return count.get(vrtx); } // Driver code public static void main(String[] args) { // Taking input int N = 4 ; List<List<Integer>> roads = new ArrayList<>(); roads.add(List.of( 1 , 2 , 3 )); roads.add(List.of( 2 , 3 , 2 )); roads.add(List.of( 4 , 3 , 2 )); // constructing a bidirectional graph using the given // input List<List<Pair>> g = new ArrayList<>(); for ( int i = 0 ; i <= N; i++) { g.add( new ArrayList<>()); } for (List<Integer> road : roads) { int u = road.get( 0 ); int v = road.get( 1 ); int w = road.get( 2 ); g.get(u).add( new Pair(v, w)); g.get(v).add( new Pair(u, w)); } // visited array List<Integer> vis = new ArrayList<>(N + 1 ); for ( int i = 0 ; i <= N; i++) { vis.add( 0 ); } // count array to keep track of the number of vertices on // the left and right side of every vertex List<Integer> count = new ArrayList<>(N + 1 ); for ( int i = 0 ; i <= N; i++) { count.add( 0 ); } // initialize answer to 0 int [] ans = { 0 }; // dfs call to calculate the result dfs(g, vis, count, N, 1 , ans); System.out.println(ans[ 0 ]); } } class Pair { int first, second; public Pair( int first, int second) { this .first = first; this .second = second; } } // This code is contributed by shivamgupta0987654321 |
Python3
class Pair: def __init__( self , first, second): self .first = first self .second = second def dfs(g, vis, count, n, vrtx, ans): # mark the current node visited vis[vrtx] = 1 # increment the count of vertex by 1 count[vrtx] = 1 # dfs call on every neighbour of current vertex for child in g[vrtx]: cv, wt = child.first, child.second if vis[cv] = = 0 : count[vrtx] + = dfs(g, vis, count, n, cv, ans) # x and y store the number of vertices on left # and right side of vrtx x, y = count[cv], n - count[cv] # add the contribution of the current wt to the ans ans[ 0 ] + = min (x, y) * 2 * wt return count[vrtx] # Driver code if __name__ = = "__main__" : # Taking input N = 4 roads = [[ 1 , 2 , 3 ], [ 2 , 3 , 2 ], [ 4 , 3 , 2 ]] # constructing a bidirectional graph using the given input g = [[] for _ in range (N + 1 )] for road in roads: u, v, w = road g[u].append(Pair(v, w)) g[v].append(Pair(u, w)) # visited array vis = [ 0 ] * (N + 1 ) # count array to keep track of the number of vertices on # the left and right side of every vertex count = [ 0 ] * (N + 1 ) # initialize answer to 0 ans = [ 0 ] # dfs call to calculate the result dfs(g, vis, count, N, 1 , ans) print (ans[ 0 ]) #This code is contributed by aeroabrar_31 |
C#
using System; using System.Collections.Generic; class MainClass { // Function to perform DFS on the graph static int dfs(List<List<Tuple< int , int >>> g, List< int > vis, List< int > count, int n, int vrtx, ref int ans) { // Mark the current node visited vis[vrtx] = 1; // Increment the count of the vertex by 1 count[vrtx] = 1; // Iterate through each neighbor of the current vertex foreach ( var child in g[vrtx]) { int cv = child.Item1; int wt = child.Item2; // If the neighbor hasn't been visited, perform DFS on it if (vis[cv] == 0) { count[vrtx] += dfs(g, vis, count, n, cv, ref ans); int x = count[cv]; int y = n - x; // Add the contribution of the current weight to the answer ans += Math.Min(x, y) * 2 * wt; } } return count[vrtx]; } public static void Main ( string [] args) { int N = 4; // Input roads represented as a list of lists List<List< int >> roads = new List<List< int >> { new List< int > { 1, 2, 3 }, new List< int > { 2, 3, 2 }, new List< int > { 4, 3, 2 } }; // Constructing the graph List<List<Tuple< int , int >>> g = new List<List<Tuple< int , int >>>(); for ( int i = 0; i <= N; i++) { g.Add( new List<Tuple< int , int >>()); } // Building bidirectional edges in the graph for ( int i = 0; i < N - 1; i++) { int u = roads[i][0]; int v = roads[i][1]; int w = roads[i][2]; g[u].Add( new Tuple< int , int >(v, w)); g[v].Add( new Tuple< int , int >(u, w)); } // Visited array to track visited vertices List< int > vis = new List< int >(); // Count array to keep track of vertices on each side List< int > count = new List< int >(); // Initializing visited and count arrays for ( int i = 0; i <= N; i++) { vis.Add(0); count.Add(0); } int ans = 0; // Perform DFS starting from vertex 1 dfs(g, vis, count, N, 1, ref ans); // Print the final result Console.WriteLine(ans); } } |
Javascript
function dfs(g, vis, count, n, vrtx, ans) { vis[vrtx] = 1; count[vrtx] = 1; for (let child of g[vrtx]) { let cv = child[0]; let wt = child[1]; if (!vis[cv]) { count[vrtx] += dfs(g, vis, count, n, cv, ans); let x = count[cv]; let y = n - x; ans[0] += Math.min(x, y) * 2 * wt; } } return count[vrtx]; } // Driver code function main() { let N = 4; let roads = [[1, 2, 3], [2, 3, 2], [4, 3, 2]]; let g = Array.from({ length: N + 1 }, () => []); for (let i = 0; i < N - 1; i++) { let u = roads[i][0]; let v = roads[i][1]; let w = roads[i][2]; g[u].push([v, w]); g[v].push([u, w]); } let vis = Array(N + 1).fill(0); let count = Array(N + 1).fill(0); let ans = [0]; dfs(g, vis, count, N, 1, ans); console.log(ans[0]); } main(); |
18
Time Complexity: O(N) where N is the number of vertices in the graph
Auxiliary Space: O(N)