记录编号	61880	评测结果	AAAAAAAAAAA
题目名称	子集	最终得分	100
用户昵称	QhelDIV	是否通过	通过
代码语言	C++	运行时间	0.198 s
提交时间	2013-06-17 16:52:02	内存使用	3.93 MiB

#include <cstdio>
#include <cstring>
#include <iostream>
#define F_I "subseta.in"
#define F_O "subseta.out"
using namespace std;
const int Nx=20000;
int N,M,Val[Nx],cn,A[Nx],B[Nx];
class Node{
public:
	int n;
	Node *pr;
}*Adj[Nx];
void add(int u,int v){
Node *p=new Node;
	p->n=v,p->pr=Adj[u],Adj[u]=p;
}
void init(){
int i,u,v;
	memset(Adj,0,sizeof(Adj));
	scanf("%d",&N);
	for(i=1;i<=N;i++){
		scanf("%d",Val+i);
		A[i]=Val[i];
	}
	scanf("%d",&M);
	for(i=1;i<=M;i++){
		scanf("%d%d",&u,&v);
		add(u,v);
		add(v,u);
	}
}
int stack[Nx],sn,Index,low[Nx],dfo[Nx],li[Nx],ln;
bool InS[Nx];
int f[Nx][2];//"0" choose 1  "1" don't
void dp(int pos){
int i;
	memset(f,0,sizeof(f));
	f[ln][0]=A[li[ln]];
	f[ln][1]=B[li[ln]];
	f[ln-1][0]=f[ln][0]+B[li[ln-1]];
	for(i=ln-2;i>=2;i--)
		f[i][0]=max(f[i+2][0]+A[li[i]]+B[li[i+1]],f[i+1][0]+B[li[i]]);
	f[i][0]=f[i+1][0]+B[li[i]];
	for(i=ln-1;i>=1;i--)
		f[i][1]=max(f[i+2][1]+A[li[i]]+B[li[i+1]],f[i+1][1]+B[li[i]]);
	A[pos]=f[1][0];
	B[pos]=f[1][1];
}
void tarjan(int pos,int fa){
	stack[++sn]=pos; 
	InS[pos]=true;
	low[pos]=dfo[pos]=++Index;
	for(Node *p=Adj[pos];p;p=p->pr)
		if(p->n!=fa){
			if(!dfo[p->n]){
				tarjan(p->n,pos);
				low[pos]=min(low[pos],low[p->n]);
				if(low[p->n]>=dfo[pos]){
				int i;
					ln=0;
					do{
						i=stack[sn--];
						li[++ln]=i;
						InS[i]=false;
					}while(stack[sn]!=pos);
					li[++ln]=pos;
					dp(pos);
				}
			}
			else
				if(InS[p->n])
					low[pos]=min(low[pos],dfo[p->n]);
		}
}
int main(){
freopen(F_I,"r",stdin);
freopen(F_O,"w",stdout);
	init();
	stack[0]=-1;
int ans=0;
	for(int i=1;i<=N;i++)
		if(!dfo[i]){
			tarjan(i,-1);
			ans+=max(A[i],B[i]);
		}
	printf("%d\n",ans);
	fclose(stdin);
	fclose(stdout);
	return 0;
}