Removing a Node

Question

The toy consists of n parts and m ropes. Each rope links two parts, but every pair of parts is linked by at most one rope. To split the toy, the child must remove all its parts. The child can remove a single part at a time, and each remove consume an energy. Let's define an energy value of part i as vi. The child spend vf1 + vf2 + ... + vfk energy for removing part i where f1, f2, ..., fk are the parts that are directly connected to the i-th and haven't been removed.

Solution Suggests that :The best way to delete all n nodes is deleting them in decreasing order of their value.

Code:

int n = in.nextInt();
int m = in.nextInt();
int[] w = new int[n]; 
for(int i=0;i<n;i++) {w[i]=in.nextInt();
}

int[] c = new int[n];
int ans =0;
for(int i=0;i<m;i++){
    int xx = in.nextInt();
    int yy = in.nextInt();
   ans+= Math.min(w[--xx],w[--yy]);
}
System.out.println(ans);

}
}

Please Explain the statement best way to delete all n nodes is deleting them in decreasing order. why we are adding only on codt of one node only? Problem LInk

Answer 1

Here is a proof of its correctness(I will use terms 'vertices', 'edges' and 'pay' instead of 'parts', 'ropes' and 'spend energy' in my proof).

1. The answer produced by this solution is not greater then the the optimal one. Let's take a look at one edge. One of the vertices will be deleted after the other. We have to pay for the one that is the deleted later. That's why for each edge we have to pay at least min(cost[v], cost[u]).

2. The optimal answer is not greater than the one produced by this algorithm. Let's remove vertices in a decreasing order of their cost. For each edge, the cheaper vertex will be the last to be removed. That's why we will pay exactly min(cost[v], cost[u]) for it.

So we have proved that the optimal answer cannot be greater and cannot be less than the answer produced by this algorithm. Thus, it is optimal(a >= b and a <= b implies a = b).