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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
#define ll long long
#define INF 2000000000
int n,m,k,g[200001];
struct fiolka{int r,krok; vector<int> d;} f[200001];
struct para{int i,krok,c,d;} p[500001];
bool fc(const para &a, const para &b) {
	if (a.krok==b.krok) return a.i<b.i;
	return a.krok<b.krok;
}
vector<int> reagenci[200001];
int col[200001];  
void TarjanOLCA(int u);

int main(int argc, char** argv) {
	ios_base::sync_with_stdio(0);
	cin >> n >> m >>  k;
	for (int i=1;i<=n;i++) cin >> g[i];
	for (int i=1;i<=m;i++) {
		int a,b;
		cin >> a >> b;
		f[a].r=b;
		f[a].krok=i;
		f[b].d.push_back(a);
	}
	for (int i=1;i<=k;i++) {
		int c,d;
		cin >> c >> d;
		p[i].c=c;p[i].d=d; p[i].i=i; p[i].krok=INF;
		reagenci[c].push_back(i);
		reagenci[d].push_back(i);
	}
	for (int i=1;i<=n;i++) {
		if (f[i].r==0)
			TarjanOLCA(i);
	}	
	sort(p+1,p+k+1,fc);
	//for (int i=1;i<=k;i++)	cout << p[i].i << ": " << p[i].krok << '\n';
	ll ans=0;
	for (int i=1;i<=k && p[i].krok<INF;i++) {
		int gmin=min(g[p[i].c],g[p[i].d]);
		if (gmin>0) {
			ans+=2*gmin;
			g[p[i].c]-=gmin;
			g[p[i].d]-=gmin;
		}
	}
	cout << ans << '\n';
	return 0;
}

struct zr{int parent,edge;} tab[200001];

void MakeSet(int x) {
    tab[x].parent = x;
    tab[x].edge = 0;
}

int Find(int x,int &edge) {
     if (tab[x].parent == x) {
        return x;
     }
     else {
     	edge = tab[x].edge;
        int r = Find(tab[x].parent,edge);
        tab[x].edge = edge;
        tab[x].parent =r;
        //cout <<"dla " << x << " p=" << r << " e=" << edge << "\n";
        return r;
     }
}

void Union(int x, int y){
	int ex,ey;
    int xRoot = Find(x,ex);
    int yRoot = Find(y,ey);
	if (xRoot != yRoot) {
         tab[yRoot].parent = xRoot;
         tab[yRoot].edge = f[yRoot].krok;
     }
}

vector<int> szuk[200001];
void TarjanOLCA(int u) {
     MakeSet(u);
     //u.ancestor := u
     //dla każdego v należącego do u.children wykonaj
     for (int i=0;i<f[u].d.size();i++) {
     	int v=f[u].d[i];
        TarjanOLCA(v);
        Union(u,v);
        //cout << "dodalem " << v << " do " << u << " p=" << tab[v].parent << " e=" << tab[v].edge << '\n';
         //Find(u).ancestor := u
     }
     col[u] = 1;
     //cout << u << " gotowe" << '\n';
     //dla każdego v takiego, że {u,v} należy do P wykonaj
     for (int i=0;i<reagenci[u].size();i++) {
     	int k=reagenci[u][i];
     	int v=p[k].c;
     	if (v==u) v=p[k].d;
        if (col[v] == 1) {
        	int e;
        	//cout << "szukam wspólnego przodka dla " << u << " i " << v << "\n";
        	szuk[Find(v,e)].push_back(k);
        }
     }
     for (int i=0;i<szuk[u].size();i++) {
     	int k = szuk[u][i];
        int e;
        Find(p[k].c,e); Find(p[k].d,e);
        //cout << " mam dla k=" << k << "  c.edge=" << tab[p[k].c].edge << " d.edge=" << tab[p[k].d].edge << '\n';
        p[k].krok=max(tab[p[k].c].edge,tab[p[k].d].edge);
     }
}