Removing Node
The toy consists of n parts and m ropes. Each rope connects two pieces, but each pair of pieces is connected by at most one rope. To break a toy, a child must remove all parts of it. A child can remove one piece at a time, and each one destroys energy. Let us define the energy value of the i part as vi. The child conducts vf1 + vf2 + ... + vfk energy to remove the part i, where f1, f2, ..., fk are the parts that are directly related to the i-th and are not removed.
<w>
Solution Suggests the following: The best way to remove all n nodes is to remove them in descending 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);
}
}
Explain the instruction to remove all n nodes by removing them in descending order. why do we only add one node to codt? LInk problem
source to share
Here is a proof that it is correct (I will use the terms "tops", "edges" and "pay" instead of "parts", "ropes" and "waste energy" in my proof).
-
The answer obtained by this solution is not more than optimal. Let's take a look at one edge. One of the vertices will be removed after the other. We have to pay for the one that was removed later. Therefore, for each edge, we must pay at least
min(cost[v], cost[u])
. -
The optimal answer is no greater than the one generated by this algorithm. Let the vertices be removed in descending order of their value. For each edge, the cheaper vertex will be removed. That is why we will pay exactly
min(cost[v], cost[u])
for this.
So, we have proved that the optimal answer cannot be greater and cannot be less than the answer obtained by this algorithm. So it is optimal ( a >= b and a <= b
means a = b
).
source to share
Not a formal proof, just help you understand:
Each rope must be "cut" to break the toy. And each rope connects two pieces to minimize the total energy, you decide to cut the rope from the "low energy" piece.
How do you achieve this by removing one piece at a time? You remove the part in descending order (you always use less energy for each rope).
But calculate the minimum energy by simply adding less energy for each rope (which is exactly what the code does).
source to share