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

#include <set>
#include <list>

#define MAXN 200002
#define MAXK 500002

using namespace std;

struct Pair {
  int x;
  int y;
};

Pair Sb[MAXN];
Pair St[MAXN];
Pair R[MAXK];
set<int> CR[MAXN];
list<int> FS[MAXN];

typedef set<int>::iterator Sit;
typedef list<int>::iterator Lit;

int m,n,k;

int main()
{
  ios_base::sync_with_stdio(0);
  
  cin >> n >> m >> k;

  long long g = 0;
  int r;
  
  for(int i=1; i<=n; ++i)
  {
    cin >> Sb[i].x;
    Sb[i].y = i;
    
    FS[i].push_back(i);
  }
  
  for(int i=0; i<m; ++i)
  {
    cin >> St[i].x >> St[i].y;
  }
  
  for(int i=0; i<k; ++i)
  {
    cin >> R[i].x >> R[i].y;
    CR[R[i].x].insert(i);
  }
  
  for(int i=0; i<m; ++i)
  {    
      CR[St[i].y].insert(CR[St[i].x].begin(), CR[St[i].x].end());
      
      for(Lit it=FS[St[i].x].begin(); it!=FS[St[i].x].end(); ++it)
      {
        if(Sb[*it].x>0)
        {
          Sb[*it].y = St[i].y;
          FS[St[i].y].push_back(*it);
        }
      }
      
      for(Sit it=CR[St[i].y].begin(); it!=CR[St[i].y].end();)
      {
        if (Sb[R[*it].x].y==St[i].y && Sb[R[*it].y].y==St[i].y)
        {
          r = min(Sb[R[*it].x].x, Sb[R[*it].y].x);
          g += 2*r;
          Sb[R[*it].x].x -= r;
          Sb[R[*it].y].x -= r;
          it = CR[St[i].y].erase(it);
        }
        else if(Sb[R[*it].x].x==0 || Sb[R[*it].y].x==0)
        {
          it = CR[St[i].y].erase(it);
        }
        else
        {
          ++it;
        }
      }
  }
      
  cout << g << endl;
  return 0;
}