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