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
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <list>
using namespace std;

typedef unsigned long long ull;

#define NMAX 200000
int ilosc[NMAX];
list<int> substancje[NMAX];
map<pair<int, int>, int> reakcja; // substancje, priorytet

int a[NMAX];
int b[NMAX];

class reakcjac{
public:
	reakcjac(int aa, int bb, int pp):a(aa),b(bb),p(pp){}
	int a, b, p;
	bool operator<(const reakcjac& right)const{
		return p < right.p;
	}
};

ull przelej(list<int>& from, list<int>& to){
	ull result = 0ull;
	map<pair<int, int>, int>::iterator it;
	vector<reakcjac> r;
	list<int>::iterator i;
	list<int>::iterator j;
	for (i = from.begin(); i != from.end(); ++i){
		for (j = to.begin(); j != to.end(); ++j){
			it = reakcja.find(pair<int, int>(*i, *j));
			if (it != reakcja.end()){
				r.push_back(reakcjac(*i, *j, it->second));
			}
		}
	}
	sort(r.begin(), r.end());
	for (int i = 0; i < (int)r.size(); i++){
		int& ia = ilosc[r[i].a];
		int& ib = ilosc[r[i].b];
		int min = ia < ib ? ia : ib;
		ia -= min; ib -= min;
		result += (2 * min);
	}
	to.insert(to.end(), from.begin(), from.end());
	from.clear();
	for (list<int>::iterator it = to.begin(); it != to.end();){
		if (ilosc[*it] == 0){
			it = to.erase(it);
		}
		else{
			++it;
		}
	}
	return result;
}

int main(){
	cin.sync_with_stdio(false);
	int n, m, k;
	cin >> n >> m >> k;
	ull osad = 0ull;

	for (int i = 0; i < n; i++){
		cin >> ilosc[i];
		if (ilosc[i]>0)substancje[i].push_back(i);
	}
	for (int i = 0; i < m; i++){
		cin >> a[i] >> b[i]; a[i]--; b[i]--;
	}
	
	int tmp1, tmp2;
	for (int i = 0; i < k; i++){
		cin >> tmp1 >> tmp2;
		reakcja[pair<int, int>(tmp1-1, tmp2-1)] = i;
		reakcja[pair<int, int>(tmp2-1, tmp1-1)] = i;
	}

	// main loop
	for (int i = 0; i < m; i++){
		osad += przelej(substancje[a[i]], substancje[b[i]]);
	}

	cout << osad << endl;
	return 0;
}