记录编号	39078	评测结果	AAAAAWAAAAA
题目名称	子集	最终得分	90
用户昵称	CC	是否通过	未通过
代码语言	C++	运行时间	0.057 s
提交时间	2012-07-04 14:59:52	内存使用	0.54 MiB

#include <cstdio>
#include <algorithm>
#include <cstring>
#define INF 1000000000
const int maxn = 10005,end = 20040;
using namespace std;
struct edge {
	int y,c;
	edge *next,*opt;
	edge (int y,int c,edge *next): y(y),c(c),next(next) {};
}*d[20050];
int n,m,tot;
int a[20050],level[20050];
void create(int x,int y,int c) {
	d[x] = new edge(y,c,d[x]);
	d[y] = new edge(x,0,d[y]);
	d[x]->opt = d[y];d[y]->opt = d[x];
}
bool bfs() {
	int head = 0,tail = 0,q[100000] = {0};
	memset(level,-1,sizeof(level));
	level[0] = 0;
	while (head <= tail) {
		int now = q[head++];
		for (edge *p = d[now];p;p = p->next)
			if (level[p->y] == -1 && p->c) 
				level[q[++tail] = p->y] = level[now] + 1;
	}
	return level[end] != -1;
}
int extend(int u,int sum) {
	int o = 0,tmp = 0;
	if (u == end) return sum;
	for (edge *p = d[u];p && o < sum;p = p->next)
		if (level[p->y] == level[u] + 1 && p->c) {
			tmp = p->c;
			if (tmp > sum - o) tmp = sum - o;
			tmp = extend(p->y,tmp);
			o += tmp;p->c -= tmp;p->opt->c += tmp;
		}
	if (!o) level[u] = -1;
	return o;
}
inline int dinic() {
	int tmp = 0,u = 0;
	while (bfs())
		while ((u = extend(0,INF)))
			tmp += u;
	return tmp;
}
		
int main() {
	freopen("subseta.in","r",stdin);
	freopen("subseta.out","w",stdout);
	scanf("%d", &n);
	for (int i = 1;i <= n;i++) {
		scanf("%d", &a[i]);
		tot += a[i];
		create(0,i,a[i]);
		create(i + maxn,end,a[i]);
	}
	scanf("%d", &m);
	int p,q;
	for (int i = 1;i <= m;i++) {
		scanf("%d%d", &p, &q);
		create(p,q + maxn,INF);
		create(q,p + maxn,INF);
	}
	int ans = dinic();
	if (ans % 2) ans = ans / 2 + 1;else ans /= 2;
	printf("%d\n", tot - ans);
	return 0;
}