Снятие узла

Question

Игрушка состоит из n частей и веревок. Каждая веревка соединяет две части, но каждая пара частей соединена не более чем одним канатом. Чтобы разбить игрушку, ребенок должен удалить все его части. Ребенок может удалить одну часть за раз, и каждый из них уничтожает энергию. Определим энергетическое значение части i как vi. Ребенок проводит vf1 + vf2 + ... + vfk энергию для удаления части i, где f1, f2, ..., fk - это части, которые непосредственно связаны с i-м и не удалены.

Решение Предлагает следующее: Лучший способ удалить все n узлов - удалить их в порядке убывания их значения.

Код:

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); 

} 
} 

Объясните, пожалуйста, лучший способ заявление, чтобы удалить все п узлов удаляет их в порядке убывания. почему мы добавляем только код только одного узла? Problem LInk

Answer 1

Это доказательство его правильности (я буду использовать термины «вершины», «ребра» и «платить» вместо «частей», «веревки» и «тратить энергию» в моем доказательстве).

1. Ответ, полученный этим решением, не больше оптимального. Давайте посмотрим на один край. Одна из вершин будет удалена после другой. Мы должны заплатить за тот, который был удален позже. Поэтому для каждого края мы должны заплатить как минимум min(cost[v], cost[u]).

2. Оптимальный ответ не больше, чем тот, который создается этим алгоритмом. Удалим вершины в порядке убывания их стоимости. Для каждого ребра будет удалена более дешевая вершина. Вот почему мы будем платить за это min(cost[v], cost[u]).

Таким образом, мы доказали, что оптимальный ответ не может быть большим и не может быть меньше, чем ответ, полученный этим алгоритмом. Таким образом, он является оптимальным (a >= b and a <= b означает a = b).

Answer 2

Не формальное доказательство, просто помочь вам понять:

Чтобы разделить игрушку, каждый канат должен быть «отрезаны». И каждая веревка соединяет две части, чтобы свести к минимуму полную энергию, вы решили вырезать веревку из части «низкой энергии».

Как добиться этого, удалив одну деталь за раз? Вы удаляете часть в порядке убывания (для каждой веревки вы всегда потребляете меньшую энергию).

Но для вычисления минимальной энергии, просто добавляя меньшую энергию для каждой веревки (это именно то, что делает код).