比赛 |
20120709 |
评测结果 |
AAWWAAWWWWWW |
题目名称 |
聪明的推销员 |
最终得分 |
33 |
用户昵称 |
isabella |
运行时间 |
0.064 s |
代码语言 |
Pascal |
内存使用 |
34.57 MiB |
提交时间 |
2012-07-09 11:55:29 |
显示代码纯文本
var
d,pp,t,fa,dd:array[1..3000]of longint;
map:array[1..3000,0..3000]of longint;
n,i,j,p,k,ret,h,g,kk,ans,temp,r:longint;
v:array[1..3000]of boolean;
flag:boolean;
procedure add(i:longint);
begin
fillchar(v,sizeof(v),0);
k:=pp[i];inc(d[k]);fa[k]:=i;inc(temp,t[i]);
if d[k]=1 then dec(ret);
v[k]:=true;
for j:=1 to map[k,0]do
begin
kk:=map[k,j];
inc(d[kk]);fa[kk]:=i;if d[kk]=1 then dec(ret);
v[kk]:=true;
for h:=1 to map[kk,0]do
if v[map[kk,h]]=false then
begin v[map[kk,k]]:=true;
inc(d[map[kk,k]]);fa[map[kk,k]]:=i;
if d[map[kk,k]]=1 then dec(ret);
end;
end;
end;
begin
assign(input,'salenet.in');reset(input);
assign(output,'salenet.out');rewrite(output);
readln(n);
readln(p);
for i:=1to p do read(pp[i],t[i]);
readln(r);
for i:=1 to r do
begin
read(j,k);
inc(map[j,0]);map[j,map[j,0]]:=k;
end;
fillchar(d,sizeof(d),0);
ret:=n;
temp:=0;
flag:=false;
for i:=1 to p do
begin
add(i);
if(flag=false)and(ret=0)then begin ans:=temp;flag:=true;end;
end;
if ret>0 then
for i:=1 to n do
if d[i]<1 then
begin writeln('NO');writeln(i);close(input);close(output);halt;end;
{dd:=d;
fillchar(d,sizeof(d),0);
ret:=n;temp:=0;
for i:=1 to n do
if dd[i]=1 then add(fa[i]);
if ret<1 then begin writeln('YES');writeln(temp);
close(input);close(output);halt;end; }
writeln('YES');
writeln(ans);
close(input);close(output);
end.