OI题库

一个简单图是一个无向图，图中没有自环边，也没有重边，重边是指某两条边的两端顶点均相同。给你一个简单图，图中每个顶点都有一个权值，每一条边都至多属于一个简单圈，你的任务是找出这样一个顶点的集合，集合中任意两个顶点间不相邻，并且集合中顶点的权值和最大。

输入格式：
第一行为一个整数n(1<=n<=10000)，表示顶点的个数。
第二行有n个整数，(0<=每个整数<10000),第i个数表示第i个顶点的权值。
第三行有一个整数m，表示边数。
接下来的m行，每行有两个整数a,b(1<=a,b<=n),表示在顶点a,b之间有一条边。

输出格式：
对于每一个测试数据，输出一个整数，表示权值最大的独立集的权值和。

样例：
subseta.in
5
1 2 1 2 0
6
1 2
2 3
3 1
2 4
4 5
5 2

subseta.out
3