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
#include "stdio.h"
#include <set>
#include <queue>

using namespace std;

const int N=200001;
//const int M=500001;

struct reaction {
	int other, prior, me;

	reaction() : other(0), prior(0), me(0) {}
	reaction(int x, int y, int z) : other(x), prior(y), me(z) {}
	bool operator < (reaction r) const {
		return make_pair(other, prior) < make_pair(r.other, r.prior);
	}
};

set< reaction > fiolki[N];
int cap[N];
pair< int,int > steps[N];
set< reaction >::iterator begins[N];
bool q[N];

int react(int s1, int s2) {
    if(cap[s1] > cap[s2]) swap(s1,s2);
    int result = cap[s1];
	cap[s2]-=cap[s1];
    cap[s1]=0;
    return 2*result;
}

int main()
{

	int n,m,k; long long osad=0;
	scanf("%d%d%d",&n,&m,&k);
	for(int i = 1; i <= n; i++) scanf("%d", &cap[i]);
	for(int i = 0; i < m; i++) scanf("%d%d", &steps[i].first, &steps[i].second);
	int c,d;
	for(int i = 0; i < k; i++) {
		scanf("%d%d", &c, &d);
		fiolki[c].insert(reaction(d,i,c)); 
		fiolki[d].insert(reaction(c,i,d)); 
	} 

    fill(q,q+N,false);
	for(int i = 0; i < m; i++) {
		int a = steps[i].first; int b = steps[i].second;
		if(fiolki[a].size() > fiolki[b].size()) swap(fiolki[a],fiolki[b]);
//        fprintf(stderr,"fiolka %d wpada do fiolki %d\n",a,b);
		
        priority_queue< pair< int,int > > temp;
        fiolki[b].insert( reaction(N,0,0) ); // straznik
		
		for (reaction r : fiolki[a]) {
            if(q[r.me]) continue;
            q[r.me]=true;
            auto it = fiolki[b].lower_bound( reaction(r.me,0,0) );

            if( it->other == r.me ) {
//                fprintf(stderr,"substancja %d z %d\n",r.me,it->me);
                temp.push( make_pair(-(it->prior), r.me) );
                    //else temp.insert( make_pair(M, r.me) );  // z tymi nikt nie chce zareagowac
				begins[r.me]=it;
 //               fprintf(stderr,"zakolejkowalem %d z prior. %d\n",r.me,it->prior);
			}
		}

        for (reaction r : fiolki[a]) q[r.me]=false;
		
		// w tej petli przeprowadzamy reakcje
		while(!temp.empty()) {
            int substance1=temp.top().second;
 //           fprintf(stderr,"priorytet %d\n",-temp.top().first);
            temp.pop();
			if(cap[substance1]==0) continue; 
			
			// wpp pierwsza substancja moze zareagowac	
		    int substance2=begins[substance1]->me;
//		    fprintf(stderr,"mam substancje %d o pojemnosci %d\n",substance2,cap[substance2]);
			
			if( cap[substance2] != 0 ) {
//				fprintf(stderr,"mietolimy %d z %d\n",substance1,substance2);
				osad+=react(substance1,substance2);
				}

			begins[substance1]++;
            if( begins[substance1]->other==substance1 )
                temp.push( make_pair(-(begins[substance1]->prior), substance1) );
		}
		
		fiolki[b].insert( fiolki[a].begin(),fiolki[a].end() );
	}
	
    printf("%lld\n", osad);
	return 0;
}