记录编号	39116	评测结果	AAAAAAAAAAA
题目名称	子集	最终得分	100
用户昵称	fuhao	是否通过	通过
代码语言	Pascal	运行时间	0.025 s
提交时间	2012-07-04 20:49:41	内存使用	1.17 MiB

const maxn=20001;
var
 dp,f:array[0..maxn,0..1] of longint;
 stack,low,dfn,a:array[0..maxn] of longint;
 next,link:array[0..2*maxn] of longint;
 top,m,n,i,ans,tot,time,num_link,x,y,temp0,temp00,temp1:longint;
 v:array[0..maxn] of boolean;
 num:array[0..maxn] of longint;
 procedure insert(x,y:longint);
 begin inc(num_link);  next[num_link]:=a[x];
       a[x]:=num_link; link[num_link]:=y;
 end;
 function max(x,y:longint):longint;
 begin if x>y then exit(x) else exit(y); end;
 procedure dp1;
 var i,j:longint;
 begin
  dp[num[1],1]:=f[num[1],1];
  dp[num[2],1]:=-maxlongint;
  dp[num[2],0]:=dp[num[1],1]+f[num[2],0];
  for i:=3 to tot do
   begin
    dp[num[i],0]:=max(f[num[i],0],
                  max(dp[num[i-1],1],dp[num[i-1],0])+f[num[i],0]);
    dp[num[i],1]:=max(f[num[i],1],dp[num[i-1],0]+f[num[i],1]);
   end;
  temp0:=dp[num[tot],0];
  dp[num[1],0]:=f[num[1],0];
  dp[num[2],0]:=f[num[1],0]+f[num[2],0];
  dp[num[2],1]:=dp[num[1],0]+f[num[2],1];
  for i:=3 to tot do
   begin
    dp[num[i],0]:=max(f[num[i],0],
                  max(dp[num[i-1],1],dp[num[i-1],0])+f[num[i],0]);
    dp[num[i],1]:=max(f[num[i],1],dp[num[i-1],0]+f[num[i],1]);
   end;
  temp00:=dp[num[tot],0]; temp1:=dp[num[tot],1];
  f[num[tot],0]:=max(f[num[tot],0],max(temp0,temp00));
  f[num[tot],1]:=max(f[num[tot],1],temp1);
 end;
 procedure dfs(k:longint);
 var i:longint;
 begin
  time:=time+1; v[k]:=true;
  dfn[k]:=time; low[k]:=time;
  inc(top); stack[top]:=k;
  i:=a[k];
  while i<>0 do
   begin
    if not v[link[i]] then
     begin
      dfs(link[i]);
      if low[k]>low[link[i]] then low[k]:=low[link[i]];
      if dfn[k]<=low[link[i]] then
       begin
        tot:=0;
        repeat
         inc(tot);
         num[tot]:=stack[top];
         dec(top);
        until stack[top]=k;
        inc(tot); num[tot]:=k;
        dp1;
       end;
     end else
    if low[k]>dfn[link[i]] then
     low[k]:=dfn[link[i]];
    i:=next[i];
   end;
 end;
begin
 assign(input,'subseta.in'); reset(input);
 assign(output,'subseta.out'); rewrite(output);
 readln(n);
 for i:=1 to n do read(f[i,1]);
 read(m);
 for i:=1 to m do
  begin
   read(x,y);
   insert(x,y);
   insert(y,x);
  end;
 time:=0;
 for i:=1 to n do
  if dfn[i]=0 then
   begin
    dfs(i);
    ans:=ans+max(f[i,0],f[i,1]);
   end;
 writeln(ans);
 close(input); close(output);
end.