Решение задачи "Ребенок и игрушка" с Codeforces

Без пояснения   Просмотров: 8


В день детей ребенок получил в подарок от Delayyy игрушку. Но ребенок такой вредный, что он ждет — не дождется шанса сломать ее.

Игрушка состоит из n деталей, соединенных m веревочками. Каждая веревочка соединяет две детали, при этом каждая пара деталей соединена не более чем одной веревочкой. Чтобы разломать игрушку, ребенок должен оторвать все ее детали. Ребенок может отрывать по одной детали за раз, на каждое отрывание он тратит энергию. Обозначим значение энергии детали i как v i. Ребенок тратит v f 1 + v f 2 + ... + v f k энергии на отрывание детали i, где f 1, f 2, ..., f k — еще не оторванные детали, напрямую соединенные веревочками с i-й.

Помогите ребенку посчитать минимальную суммарную энергию, которую он должен потратить на отрывание всех n деталей.

Код

#include <iostream>

using namespace std;
long long int x,y,a[3000],n,m,sum;
int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++)cin>>a[i];
	for(int i=0;i<m;i++){
		cin>>x>>y;
		sum+=min(a[--x],a[--y]);
	}
	cout<<sum;

	return 0;
}

         

 Администратор Photo Автор: Администратор


Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться