Решение задачи Слух с Codeforces

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

Вова пообещал себе больше никогда не играть в игры... Но недавно компания Firestorm выпустила очень популярную игру — World of Farcraft, и Вова, конечно же, начал в неё играть.

Он впал в ступор при выполнении очередного квеста — необходимо было прийти в поселение Надгород и распространить там слух.

Вова знает, что в Надгороде живут n персонажей. Некоторые персонажи дружат между собой и готовы делиться информацией друг с другом. Также он знает, что i-й персонаж готов начать распространять слух за c i золота. Как только персонаж узнаёт слух, он рассказывает его всем своим друзьям, которые, в свою очередь, тоже начинают распространять этот слух (но уже бесплатно).

Вова хочет, чтобы слух узнали все n персонажей Надгорода. За какое минимальное количество золота он сможет это сделать?

Посмотрите примечание для лучшего понимания задачи.

Код 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100008;
ll n,m,a[N];
int findr(int x) {
	if(a[x]<=0)return x;
	return a[x]=findr(a[x]);
}

int main() {
	ios::sync_with_stdio(false);
	int i,k,p1,p2;
	cin>>n>>m;
	for(i=1;i<=n;i++){cin>>k;a[i]=-k;}
	while(m--)
	{
		cin>>p1>>p2;p1=findr(p1);p2=findr(p2);
		if(p1==p2)continue;
		if(a[p1]>a[p2]){k=p1;p1=p2;p2=k;}
		a[p1]=p2;
	}
	ll s=0;
	for(i=1;i<=n;i++)if(findr(i)==i)s-=a[i];
	cout<<s;
}

         

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




Комментарии

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


© 2020 HSECODES [email protected] Карта сайта