比赛 |
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.