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 103 #include #include #include #include using namespace std; struct Reakcja { int c, d, k; Reakcja(int _c = 0, int _d = 0, int _k = 0) : c(_c), d(_d), k(_k) {} }; bool operator< (Reakcja a, Reakcja b) { return a.k < b.k; } struct PoD { bool operator() (Reakcja a, Reakcja b) { return a.d < b.d; } }; int A[200001], B[200001], G[200001], L[200001], N[200001], O[200001]; set R[200001]; set K; int main() { int a, b, c, d, k, m, n, o; set::iterator r; 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) scanf("%d %d", A + i, B + i); for (int i = 0; i < k; ++i) { scanf("%d %d", &c, &d); if (c > d) swap(c, d); R[c].insert(Reakcja(c, d, i)); ++L[c]; ++L[d]; } long long w = 0; for (int i = 0; i < m; ++i) { a = A[i]; while (a) { b = B[i]; while (b) { if (a < b) { c = a; d = b; } else { c = b; d = a; } r = R[c].find(Reakcja(c, d)); if (r != R[c].end()) { --L[r->c]; --L[r->d]; K.insert(*r); } b = N[b]; } a = N[a]; } if (O[B[i]]) { if (O[A[i]]) { N[O[B[i]]] = A[i]; O[B[i]] = O[A[i]]; } else { N[O[B[i]]] = A[i]; O[B[i]] = A[i]; } } else { if (O[A[i]]) { N[B[i]] = A[i]; O[B[i]] = O[A[i]]; } else { N[B[i]] = O[B[i]] = A[i]; } } a = B[i]; b = N[B[i]]; while (b) { if (L[b]) { a = b; b = N[b]; } else { N[a] = N[b]; b = N[b]; } } O[B[i]] = a; while (!K.empty()) { r = K.begin(); o = min(G[r->c], G[r->d]); G[r->c] -= o; G[r->d] -= o; w += o + o; K.erase(K.begin()); } } printf("%lld\n", w); return 0; }