War with Westelande(CC024) - Editorial

editorial
, ,
1

Contest
Practice

Author : Murtaza Ali
Tester: Yash Sharma, Pranay Garg
Editorialist: Nehal Jain

DIFFICULTY : Medium

PREREQUISITES : DP, DFS

PROBLEM:
Find the minimum cost to reverse the edges of a weighted graph such that every node can be reached from vertex(s) and also print the vertex(s) from where such a traversal can be done.

QUICK EXPLANATION:
We have a graph with n vertex and n-1 edges (i.e tree),we just need to find out the most feasible node from where we can traverse the whole tree with least cost required to invert the edges.

SOLUTION:
We can solve this problem using DFS. we start dfs at any random node of given tree and at each node we store its total cost from starting node assuming all edges as undirected and we also store total cost of edges which need to be reversed in the path from starting node to current node, let’s denote such edges as red edges so red edges are those which point towards the node in a path.

In the code i[2]=0 is the reverse/red edge

Code 
void dfs(vector<vector<vector<ll>>> &tree, ll current, ll parent, ll &redsum, ll red_path[], ll pathsum[]) {
for(auto &i : tree[current]) {
    if(i[0] == parent) continue;
    red_path[i[0]] = red_path[current];
    pathsum[i[0]] = pathsum[current] + i[1];

    if(i[2] == 0) {
        redsum += i[1];
        red_path[i[0]] += i[1];
    } 

    dfs(tree, i[0], current, redsum, red_path, pathsum);
}

}

After this computation, at each node we can calculate ‘cost of edge reversal to reach every other node’ as follows:
Let total number of reversals in tree when some node is chosen as starting node for dfs is totalRev than if we want to reach every other node from node i we need to reverse all red edges from path node i to starting node and we also need to reverse all other red edges other than node i to starting node path.

First part will be
totalCostUptoI - redEdgesCostUptoI
This is because it would give us the difference of total cost upto ith node and red edges cost which in turn is the red edges cost from the perspective of node i.

Second part will be
TotalCostOfInversion(Whole Tree) - redEdgesCostUptoI
It gives us the cost of red edges for the tree other than the nodes in the path of startingNode to i which has been computed in the previous part

Finally we need to minimize the sum of the two parts i.e.
TotalCostOfInversion(Whole Tree) - 2 * redEdgesCostUptoI + totalCostUptoI

Code 
for(ll i = 1; i <= n; i++)
        min_val = min(min_val, redsum - 2*red_in_path[i] + pathsum[i]);

And the vertices that have this minimum value would then be printed.

Setter's Solution: 
#include <bits/stdc++.h>
using namespace std; 
typedef long long ll;

ll min(ll a, ll b) {
    return a < b ? a : b;
}

void dfs(vector<vector<vector<ll>>> &tree, ll current, ll parent, ll &redsum, ll red_path[], ll pathsum[]) {
for(auto &i : tree[current]) {
    if(i[0] == parent) continue;
    red_path[i[0]] = red_path[current];
    pathsum[i[0]] = pathsum[current] + i[1];

    if(i[2] == 0) {
        redsum += i[1];
        red_path[i[0]] += i[1];
    } 
    dfs(tree, i[0], current, redsum, red_path, pathsum);
   }
}

int main() {
ll t;
cin>>t;
while(t--){
    ll n;
    cin>>n;
    vector<vector<vector<ll>>> tree(n+1);
    for(ll i = 1; i < n; i++) {
        ll v, u, w;
        cin>>v>>u>>w;
        tree[v].push_back({u, w, 1});
        tree[u].push_back({v, w, 0});
    }

    ll redsum = 0, root = 1, red_in_path[n+1], pathsum[n+1];
    memset(red_in_path, 0, sizeof red_in_path);
    memset(pathsum, 0, sizeof pathsum);

    dfs(tree, root, -1, redsum, red_in_path, pathsum);

    ll min_val = 1e12;

    for(ll i = 1; i <= n; i++)
        min_val = min(min_val, redsum - 2*red_in_path[i] + pathsum[i]);

    cout<<min_val<<'\n';

    for(ll i = 1; i <= n; i++)
        if(min_val == redsum - 2*red_in_path[i] + pathsum[i]) 
            cout<<i<<' ';

    cout<<'\n';
   }
return 0;
}

Doubts and alternative solutions are welcome.

1 Like