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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <set>
using namespace std;
const int N = 200001;
int i, n, t, m, k, a, b;
long long wynik = 0;
int F[N], Z[N], DO[N], P[N];
set <pair<int, int> > REAG;
set<int> MIESZ[N];
set<int>::iterator it;
pair<int,int> KOL[500001];
vector<int> PRIOR[N];

void UNION (int a, int b) {
	if(P[a] == a && P[b] == b) { //lacze pojedyncze wierzcholki
		if( REAG.find(make_pair(min(a,b),max(a,b))) !=REAG.end()) {
			if(F[a] <= F[b]) {		
				F[b] = F[b] - F[a];
				wynik = wynik + 2*F[a];
				MIESZ[a].clear();
				P[a] = -1;
				}
			else { 
				F[a] = F[a] - F[b];
				wynik = wynik + 2*F[b];				
				MIESZ[a].clear();
				MIESZ[b].clear();
				MIESZ[b].insert(a);
				P[b] = -1;
				P[a] = -1;
			}
		}	
		else {
			P[a] = -1;
			P[b] = -1;
			MIESZ[b].insert(a);
			MIESZ[a].clear();			
		}
	}
	else if (P[a] == a) {
		for(int i = 0; i < PRIOR[a].size(); ++i) if ( MIESZ[b].find(PRIOR[a][i]) != MIESZ[b].end()) {
		int f = a, s = PRIOR[a][i];
		if(F[f] <= F[s]) {		
					F[s] = F[s] - F[f];
					P[f] = -1;
					wynik = wynik + 2*F[f];
					MIESZ[a].clear();
					}
		else { 
					F[f] = F[f] - F[s];
					wynik = wynik + 2*F[s];
					MIESZ[b].erase(MIESZ[b].find(s));
					P[s] = -1;
					}			
		}
		if(F[a] > 0) {
						MIESZ[b].insert(a);
						P[a] = -1;
						MIESZ[a].clear();
					}
						
						
		}
	else if(P[b] == b) {
		for(int i = 0; i < PRIOR[b].size(); ++i) if ( MIESZ[a].find(PRIOR[b][i]) != MIESZ[a].end()) {
		int f = PRIOR[b][i], s = b;
		if(F[f] <= F[s]) {		
					F[s] = F[s] - F[f];
					P[f] = -1;
					wynik = wynik + 2*F[f];
					MIESZ[a].erase(MIESZ[a].find(f));
					}
		else { 
					F[f] = F[f] - F[s];
					wynik = wynik + 2*F[s];
					MIESZ[s].clear();
					P[s] = -1;	
		}
		for(it = MIESZ[a].begin(); it!= MIESZ[a].end();++it) {
													MIESZ[b].insert(*it);
													P[*it]=-1;
												}
					MIESZ[a].clear();	
					}		
		}
	else
	 { //wierzcholkow w poddrzewie jest wiecej
		for(int i = 1; i <= k; ++i) {
			int f = KOL[i].first, s = KOL[i].second;
			if(MIESZ[a].find(f) !=MIESZ[a].end() && MIESZ[b].find(s) !=MIESZ[b].end()){
					if(F[f] <= F[s]) {		
					F[s] = F[s] - F[f];
					P[f] = -1;
					wynik = wynik + 2*F[f];
					MIESZ[a].erase(MIESZ[a].find(f));
					}
					else { 
					F[f] = F[f] - F[s];
					wynik = wynik + 2*F[s];
					MIESZ[b].erase(MIESZ[b].find(s));
					P[s] = -1;
					}
				}	
			else if (MIESZ[b].find(f) !=MIESZ[b].end() && MIESZ[a].find(s) !=MIESZ[a].end()){
					if(F[f] <= F[s]) {		
					F[s] = F[s] - F[f];
					P[f] = -1;
					wynik = wynik + 2*F[f];
					MIESZ[b].erase(MIESZ[b].find(f));
					}
				else { 
					F[f] = F[f] - F[s];
					wynik = wynik + 2*F[s];
					MIESZ[a].erase(MIESZ[a].find(s));
					P[s] = -1;
					}	
			}
	}
	for(it = MIESZ[a].begin(); it!= MIESZ[a].end();++it) {
													MIESZ[b].insert(*it);
													P[*it]=-1;
												}
	MIESZ[a].clear();
	
}	
}
int main() {

	scanf("%d%d%d",&n,&m,&k);
	for(i = 1; i <= n; ++i) {
		scanf("%d", &F[i]);
		MIESZ[i].insert(i);
		P[i] = i;
	}
	for(i = 1; i <= m; ++i) {
		scanf("%d%d",&Z[i],&DO[i]);
				
	}
	for(i = 1; i <= k; ++i) {
		scanf("%d%d",&a,&b);
		REAG.insert(make_pair(min(a,b),max(a,b)));
		KOL[i].first = a; KOL[i].second = b;
		PRIOR[a].push_back(b);
		PRIOR[b].push_back(a);
		
	}
	for(i = 1; i <= m; ++i){
		a = Z[i]; b = DO[i];
		UNION(a, b);
	}

	printf("%lld\n",wynik); 

return 0;
}