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
#include <cstdio>
#include <algorithm>
#include <unordered_map>
//#include <map>
using namespace std;

const int MAXF=200000;
const int MAXS=500000;
typedef unsigned long long ULL;
typedef unordered_map<int,int> G;typedef G::iterator GI;
typedef unordered_multimap<int,pair<int,int> > L;typedef L::iterator LI;
typedef pair<LI,LI> LIP;
struct F{
    G g;L l;
}f[MAXF];
struct M{
    int u,v;
}s[MAXS];
bool compSec(const pair<int,int> &a,const pair<int,int> &b){return a.second<b.second;}
void prt(G *a){for(GI i=a->begin();i!=a->end();++i)printf("(%d,%d)",i->first,i->second);}
void prt(L *a){for(LI i=a->begin();i!=a->end();++i)printf("(%d,%d)",i->first,i->second.first);}
void prt(F *a,int i){printf("[i=%d,g={",i);prt(&a->g);printf("},l={");prt(&a->l);printf("}], ");}
void prt(int n,F*a){for(int i=0;i<n;++i)prt(a+i,i);printf("\n");fflush(stdout);}
int main(){
    int n,m,k,i,g,u,v;
    scanf("%d%d%d",&n,&m,&k);
    for(i=0;i<n;++i){
        scanf("%d",&g);
        f[i].g.insert(make_pair(i,g));
    }
    for(i=0;i<m;++i){
        scanf("%d%d",&s[i].u,&s[i].v);
        --s[i].u;--s[i].v;
    }
    for(i=0;i<k;++i){
        scanf("%d%d",&u,&v);
        --u;--v;
        f[u].l.insert(make_pair(v,make_pair(u,i)));
        f[v].l.insert(make_pair(u,make_pair(v,i)));
    }
    ULL z=0;vector<pair<int,int> >cc;
////    prt(n,f);
    for(i=0;i<m;++i){
        u=s[i].u;v=s[i].v;
        for(GI ugi=f[u].g.begin();ugi!=f[u].g.end();++ugi){//for each source subst
            LIP vlip=f[v].l.equal_range(ugi->first);
            cc.clear();
            for(LI vli=vlip.first;vli!=vlip.second;++vli)cc.push_back(vli->second);
            f[v].l.erase(vlip.first,vlip.second);
            sort(cc.begin(),cc.end(),compSec);
            for(vector<pair<int,int> >::iterator b=cc.begin();b!=cc.end();++b){//for each complementary subst in dest
                GI vgi=f[v].g.find(b->first);
                if(vgi==f[v].g.end())
                    continue;
                int d=min(ugi->second,vgi->second);
                z+=((ULL)d)<<1;
                vgi->second-=d;
                if(vgi->second==0)
                    f[v].g.erase(vgi);
                else
                    f[v].l.insert(make_pair(vgi->second,make_pair(v,0)));// 0 is not ok
                ugi->second-=d;
                if(ugi->second==0)break;
            }
            if(ugi->second>0){
                f[v].g.insert(*ugi);
                vlip=make_pair(f[u].l.begin(),f[u].l.end());//f[u].l.equal_range(ugi->first);
                for(LI vli=vlip.first;vli!=vlip.second;++vli)
                    if(vli->second.first==u)
                        f[v].l.insert(*vli);
            }
        }
        f[u].g.clear();
        f[u].l.clear();
        if(f[v].g.empty())
            f[v].l.clear();
////        prt(n,f);
    }
    printf("%llu\n",z);
    return 0;
}