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
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#define MAKS 200010
using namespace std;
typedef long long int lld;
int tab[MAKS];
int za[MAKS]; int zb[MAKS];
map<lld, int> M;
int n,m,k;
lld koduj(int aa, int bb)
{
    int a=min(aa,bb);
    int b=max(aa,bb);
    return lld(a)*lld(n+1) + lld(b);
}
vector<int> sub[MAKS];

bool cmp(const pair<int,int> &a, const pair<int,int> &b)
{
    return M[koduj(a.first,a.second)]<M[koduj(b.first,b.second)];
}
int main()
{
    
    scanf("%d %d %d",&n,&m,&k);
    for(int i=1;i<=n;i++)scanf("%d",&tab[i]);
    for(int i=0;i<m;i++)scanf("%d %d",&za[i],&zb[i]);
    for(int i=0;i<k;i++)
    {
        int p,q;
        scanf("%d %d",&p,&q);
        M[koduj(p,q)]=i;
    }
    
    for(int i=1;i<=n;i++)sub[i].push_back(i);
    
    lld wyn=0;
    for(int i=0;i<m;i++)
    {
        int a=za[i]; int b=zb[i];
        vector< pair<int,int> > v;
        for(int j=0;j<sub[a].size();j++)
        {
            for(int k=0;k<sub[b].size();k++)
            {
                if(M.find(koduj(sub[a][j],sub[b][k]))!=M.end())
                {
                    v.push_back(make_pair(sub[a][j],sub[b][k]));
                }
            }
        }
        sort(v.begin(),v.end(),cmp);
        for(int j=0;j<v.size();j++)
        {
            int a=v[j].first; int b=v[j].second;
            int re=min(tab[a],tab[b]);
            wyn+=lld(2)*lld(re);
            tab[a]-=re; tab[b]-=re;
        }
        for(int j=0;j<sub[a].size();j++)sub[b].push_back(sub[a][j]);
        sub[a].clear();
    }
    printf("%lld\n",wyn);
}