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
#include <cstdio>
#include <algorithm>
#include <list>
//using namespace std;

const int MAXN = 200005, MAXM = 200005, MAXK = 500005;
int weight[MAXN];
std::pair<int,int> reaction[MAXM];
std::pair<int,int> sediment[MAXK];

int n,m,k;

int tab[MAXN];
int rank[MAXN];

void MakeSet(int x)
{
  tab[x]=x;
  rank[x]=1;
}

void PreapareSet(int to)
{
	for(int i = 0; i <= to; ++i)
		MakeSet(i);
}

int Find(int x)
{
  return (x==tab[x] ? x : tab[x]=Find(tab[x]));
}

bool Union(int x,int y)
{
  int fx=Find(x),fy=Find(y);
  if(fx==fy) return 0;
  rank[fx]<=rank[fy] ? rank[fy]+=rank[fx],tab[fx]=tab[fy] : rank[fx]+=rank[fy],tab[fy]=tab[fx];
  return 1;
}

bool Test(int x, int y)
{
	if(Find(x) == Find(y))
		return true; //in same set
	return false; //not in same set
}


void get()
{
	scanf("%d %d %d", &n, &m, &k);
	for(int i = 1; i <= n; ++i)
		scanf("%d", &weight[i]);
	for(int i = 1; i <= m; ++i)
		scanf("%d %d", &reaction[i].first, &reaction[i].second);
	for(int i = 1; i <= k; ++i)
		scanf("%d %d", &sediment[i].first, &sediment[i].second);
}

long long getSediment()
{
	long long result = 0;
	int removed;
	std::list<int> canBeUsed;
	for(int j = 1; j <= k; ++j)
	{
		canBeUsed.push_back(j);
	}
	for(int i = 1; i <= m; ++i){
		//xprintf("%d\n",i);
		Union(reaction[i].first, reaction[i].second);
		for(std::list<int>::iterator it = canBeUsed.begin(); it != canBeUsed.end();){
			if(Test(sediment[*it].first, sediment[*it].second) == true){
				removed = std::min(weight[sediment[*it].first], weight[sediment[*it].second]);
				result += 2*removed;
				weight[sediment[*it].first] -= removed;
				weight[sediment[*it].second] -= removed;
				it = canBeUsed.erase(it);
			}else{
				it++;
			}
		}
	}
	return result;
}

int main()
{
	get();
	PreapareSet(n);
	printf("%lld\n", getSediment());
}