比赛 20120704 评测结果 AAAAAAATEEE
题目名称 子集 最终得分 63
用户昵称 isabella 运行时间 0.000 s
代码语言 Pascal 内存使用 0.00 MiB
提交时间 2012-07-04 11:53:28
显示代码纯文本
type
 arr=array[1..1000]of boolean;
var
 x,y:array[1..1000000]of longint;
 w,s,t:array[1..10000]of longint;
 vv:arr;
 n,m,j,i,mid,temp,ans:longint;

 procedure sort(l,r:longint);
 var i,j:longint;
 begin
  i:=l;j:=r;mid:=x[(l+r)div 2];
  repeat
   while x[i]<mid do inc(i);
   while x[j]>mid do dec(j);
   if i<=j then
    begin temp:=x[i];x[i]:=x[j];x[j]:=temp;
          temp:=y[i];y[i]:=y[j];y[j]:=temp;
          inc(i);dec(j);end;
  until i>j;
  if i<r then sort(i,r);
  if l<j then sort(l,j);
 end;

 procedure dfs(k,now:longint;v:arr);
  var i:longint;
  begin
   if now>ans then ans:=now;
   v[k]:=true;
   for i:=s[k] to t[k] do v[y[i]]:=true;
   for i:=1 to n do
    if v[i]=false then dfs(i,now+w[i],v);
  end;

begin
assign(input,'subseta.in');reset(input);
assign(output,'subseta.out');rewrite(output);
 readln(n);
 for i:=1 to n do read(w[i]);
 readln(m);
 for i:=1 to m do
   begin read(x[i],y[i]);x[i+m]:=y[i];y[i+m]:=x[i];end;

 sort(1,m*2);
 i:=1;j:=0;
 while i<=m*2 do
  begin
   inc(j);s[j]:=i;
   while x[i]=j do inc(i);
   t[j]:=i-1;
  end;

 for i:=1 to n do
  begin
   fillchar(vv,sizeof(vv),0);
   for j:=s[i] to t[i] do vv[y[j]]:=true;
   dfs(i,w[i],vv);
  end;

 writeln(ans);
 close(input);close(output);
end.