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
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 200020;
const int K = 500050;

int T[N];
int KR[K][2];

int ILP[N];
int MP[N];
int MPS[N];

vector<int> F[N];
vector<pair<int,int> > R[N];
vector<pair<pair<int, int>,pair<int, int> > > G;

int main()
{
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);

    for(int i=0;i<n;++i)
        scanf("%d",&T[i]);
    for(int i=0;i<m;++i)
    {
        scanf("%d%d",&KR[i][0],&KR[i][1]);
        --KR[i][0];
        --KR[i][1];
    }

    int c,d;
    for(int i=0;i<k;++i)
    {
        scanf("%d%d",&c,&d);
        --c;
        --d;
        R[c].push_back(make_pair(d,i));
        R[d].push_back(make_pair(c,i));
    }
    if (1==n)
    {
        printf("0\n");
        return 0;
    }

    for(int i=0;i<n;++i)
    {
        MP[i]=i;
        MPS[i]=i;
        ILP[i]=R[i].size();
        F[i].push_back(i);
    }

    for(int i=0;i<m;++i)
    {
        int s=MP[KR[i][0]];
        int t=MP[KR[i][1]];
        if (ILP[s]>ILP[t])
            swap(t,s);
        for(int f=0;f<F[s].size();++f)
        {
            int SZ = R[F[s][f]].size();
            if (0 < SZ)
            {
                for(int j=0;j<SZ;++j)
                {
                    int p=R[F[s][f]][j].first;
                    if (MPS[p]==t) {
                        G.push_back(make_pair(make_pair(i,R[F[s][f]][j].second), make_pair(p, F[s][f])));
                            //cout << "A: " << p << " " << F[s][f] << endl;
                            //cout << s << " " << t << endl;
                    }
                }

                MPS[F[s][f]]=t;
                F[t].push_back(F[s][f]);

            }
        }
        MP[KR[i][0]]=MP[KR[i][1]]=t;
        ILP[t]+=ILP[s];
    }
    sort(G.begin(), G.end());
    long long W = 0L;
    for(int i=0;i<G.size();++i)
    {
        pair<int,int> p=G[i].second;
        int mn=min(T[p.first],T[p.second]);
        W += mn + mn;
        //cout << mn << " " << p.first << " " << p.second << endl;
        //cout << T[p.first] << " " << T[p.second] << endl;
        T[p.first]-=mn;
        T[p.second]-=mn;
    }
    cout << W << endl;
    return 0;
}