比赛 20120709 评测结果 AAWWAAWWWWWW
题目名称 聪明的推销员 最终得分 33
用户昵称 isabella 运行时间 0.064 s
代码语言 Pascal 内存使用 34.57 MiB
提交时间 2012-07-09 11:55:29
显示代码纯文本
  1. var
  2. d,pp,t,fa,dd:array[1..3000]of longint;
  3. map:array[1..3000,0..3000]of longint;
  4. n,i,j,p,k,ret,h,g,kk,ans,temp,r:longint;
  5. v:array[1..3000]of boolean;
  6. flag:boolean;
  7.  
  8. procedure add(i:longint);
  9. begin
  10. fillchar(v,sizeof(v),0);
  11. k:=pp[i];inc(d[k]);fa[k]:=i;inc(temp,t[i]);
  12. if d[k]=1 then dec(ret);
  13. v[k]:=true;
  14. for j:=1 to map[k,0]do
  15. begin
  16. kk:=map[k,j];
  17. inc(d[kk]);fa[kk]:=i;if d[kk]=1 then dec(ret);
  18. v[kk]:=true;
  19. for h:=1 to map[kk,0]do
  20. if v[map[kk,h]]=false then
  21. begin v[map[kk,k]]:=true;
  22. inc(d[map[kk,k]]);fa[map[kk,k]]:=i;
  23. if d[map[kk,k]]=1 then dec(ret);
  24. end;
  25. end;
  26. end;
  27.  
  28. begin
  29. assign(input,'salenet.in');reset(input);
  30. assign(output,'salenet.out');rewrite(output);
  31. readln(n);
  32. readln(p);
  33. for i:=1to p do read(pp[i],t[i]);
  34. readln(r);
  35. for i:=1 to r do
  36. begin
  37. read(j,k);
  38. inc(map[j,0]);map[j,map[j,0]]:=k;
  39. end;
  40.  
  41. fillchar(d,sizeof(d),0);
  42. ret:=n;
  43. temp:=0;
  44. flag:=false;
  45. for i:=1 to p do
  46. begin
  47. add(i);
  48. if(flag=false)and(ret=0)then begin ans:=temp;flag:=true;end;
  49. end;
  50.  
  51. if ret>0 then
  52. for i:=1 to n do
  53. if d[i]<1 then
  54. begin writeln('NO');writeln(i);close(input);close(output);halt;end;
  55.  
  56. {dd:=d;
  57. fillchar(d,sizeof(d),0);
  58. ret:=n;temp:=0;
  59. for i:=1 to n do
  60. if dd[i]=1 then add(fa[i]);
  61. if ret<1 then begin writeln('YES');writeln(temp);
  62. close(input);close(output);halt;end; }
  63.  
  64. writeln('YES');
  65. writeln(ans);
  66. close(input);close(output);
  67. end.