1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#define ll long long
using namespace std;

//nie mam zielonego pojecia czemu nie dziala

struct doReakcji
{
	int kto, zkim, nr;
	doReakcji(int a, int b, int c):kto(a), zkim(b), nr(c){}
};
bool operator < (doReakcji a, doReakcji b) {return a.zkim<b.zkim;}
bool porownajPoNumerze( doReakcji a, doReakcji b) {return a.nr<b.nr;}
struct fiolka
{
	set<int> substancje;
	set<doReakcji> reakcje;
};

fiolka tab[200009];
ll gramy[200009];
ll wynik=0;
vector<pair<int, int> >kroki;
vector<pair<int, int> >pary;

void junion(int a, int b);

int main()
{
	int lfiolek, lkrokow, lpar;
	cin>>lfiolek>>lkrokow>>lpar;
	for(int n=1; n<=lfiolek; n++)
	{
		tab[n].substancje.insert(n);
		cin>>gramy[n];
	}
	int tmpa, tmpb;
	for(int n=0; n<lkrokow; n++)
	{
		cin>>tmpa>>tmpb;
		kroki.push_back(make_pair(tmpa, tmpb));
	}
	for(int n=0; n<lpar; n++)
	{
		cin>>tmpa>>tmpb;
//		pary.push_back(make_pair(tmpa, tmpb));
		tab[tmpa].reakcje.insert(doReakcji(tmpa, tmpb, n+1));
		tab[tmpb].reakcje.insert(doReakcji(tmpb, tmpa, n+1));
	}
	
	for(int n=0; n<lkrokow; n++)
	{
//		cout<<" "<<kroki[n].first<<" "<<kroki[n].second<<endl;
		junion(kroki[n].first, kroki[n].second);
//		cout<<wynik<<endl;
	}
	
	cout<<wynik<<endl;
}

void junion(int b, int a)
{
	vector<doReakcji> bedzieReagowac;
	int swapped=0;
//	if(tab[a].substancje.size()<tab[b].substancje.size()) {swap(a, b); swapped=1;}
	for(auto it=tab[b].substancje.begin(); it!=tab[b].substancje.end(); it++)
	{
		
		for(auto n=tab[a].reakcje.lower_bound(doReakcji(0, *it, 0)); n!=tab[a].reakcje.upper_bound(doReakcji(0, *it, 0)); n++)
		{
			bedzieReagowac.push_back(*n);
//			tab[a].reakcje.erase(*n);		//not sure
		}
	}
	sort(bedzieReagowac.begin(), bedzieReagowac.end(), porownajPoNumerze);
	for(int n=0; n<bedzieReagowac.size(); n++)
	{
//		cout<<"     "<<bedzieReagowac[n].kto<<" reaguje z "<<bedzieReagowac[n].zkim<<endl;
		int tmp=min(gramy[bedzieReagowac[n].zkim], gramy[bedzieReagowac[n].kto]);
//		cout<<"tmp="<<tmp<<endl;
		wynik+=2*tmp;
		gramy[bedzieReagowac[n].zkim]-=tmp; gramy[bedzieReagowac[n].kto]-=tmp;
//		if(gramy[bedzieReagowac[n].zkim]==0)
//		{
//			if( tab[b].substancje.count(bedzieReagowac[n].zkim)>0 )
//				tab[b].substancje.erase(bedzieReagowac[n].zkim);
//		}
//		if(gramy[bedzieReagowac[n].kto]==0)
//		{
//			if( tab[a].substancje.count(bedzieReagowac[n].kto)>0 )
//				tab[a].substancje.erase(bedzieReagowac[n].kto);
//		}
	}
	if(swapped) swap(a,b);

	tab[a].substancje.insert(tab[b].substancje.begin(), tab[b].substancje.end());
	tab[a].reakcje.insert(tab[b].reakcje.begin(), tab[b].reakcje.end());

//	tab[b].substancje.clear();
//	tab[b].reakcje.clear();
//	cout<<"elementy zbioru "<<a<<": ";
//	for(auto n= tab[a].substancje.begin();n!=tab[a].substancje.end(); n++)
//	{
//		cout<<*n<<" ";
//	}
//	cout<<endl;

}