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
#include <cstdio>
#include <cstdlib>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

struct pouring {
  int from, to;
};

struct reaction {
  int a, b;
};

int g[200000 + 2];
vector<pouring> pourings;
vector<reaction> reactions;
set<int> flasks[200000 + 2];
int aliases[200000 + 2];

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

  for (int i = 1; i <= n; i++) {
    scanf("%d", &g[i]);
  }

  for (int i = 0; i < m; i++) {
    pouring p;
    scanf("%d%d", &p.from, &p.to);
    pourings.push_back(p);
  }

  for (int i = 0; i < k; i++) {
    reaction r;
    scanf("%d%d", &r.a, &r.b);
    flasks[r.a].insert(reactions.size());
    flasks[r.b].insert(reactions.size());
    reactions.push_back(r);
  }

  // Follow the pouring process as described on input.
  long long wyn = 0;
  for (int i = 0; i < pourings.size(); i++) {
    int from = pourings[i].from;
    int to = pourings[i].to;
    bool swapped = false;

    if (aliases[from]) {
      from = aliases[from];
    }
    if (aliases[to]) {
      to = aliases[to];
    }

    if (flasks[from].size() > flasks[to].size()) {
      swap(from, to);
      swapped = true;
    }

    for (set<int>::iterator it = flasks[from].begin(); it != flasks[from].end(); it++) {
      if (flasks[to].find(*it) != flasks[to].end()) {
        int mm = min(g[reactions[*it].a], g[reactions[*it].b]);
        g[reactions[*it].a] -= mm;
        g[reactions[*it].b] -= mm;
        wyn += 2 * mm;
        flasks[to].erase(*it);
      } else {
        flasks[to].insert(*it);
      }
    }

    if (swapped) {
      aliases[pourings[i].to] = to;
    }
  }

  printf("%lld\n", wyn);
  return 0;
}