epidemic - Random.PAS 1.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101
  1. { Created by Weidong Hu, Jan.19, 2005 }
  2. const
  3. inf = 'epidemic.in';
  4. ouf = 'epidemic.out';
  5. maxn = 300;
  6. type
  7. xtype = array[0..maxn] of integer;
  8. var
  9. linker : array[1..maxn] of ^xtype;
  10. ill : array[1..maxn] of byte;
  11. ti : integer;
  12. ills : array[1..maxn] of integer;
  13. n : integer;
  14. ans : integer;
  15. procedure prepare;
  16. var
  17. i : integer;
  18. begin
  19. for i := 1 to maxn do
  20. begin
  21. new(linker[i]);
  22. linker[i]^[0] := 0;
  23. end;
  24. end;
  25. procedure init;
  26. var
  27. i, a, b : integer;
  28. begin
  29. assign(input, inf); reset(input);
  30. read(n, a);
  31. for i := 1 to n - 1 do
  32. begin
  33. read(a, b);
  34. inc(linker[a]^[0]); linker[a]^[linker[a]^[0]] := b;
  35. inc(linker[b]^[0]); linker[b]^[linker[b]^[0]] := a;
  36. end;
  37. close(input);
  38. end;
  39. procedure main;
  40. var
  41. ii, i, j : integer;
  42. w, a : integer;
  43. total : integer;
  44. begin
  45. randSeed := 19860805;
  46. ans := n;
  47. for ii := 1 to 20000 do
  48. begin
  49. fillchar(ill, sizeof(ill), 0);
  50. ill[1] := 1;
  51. ills[1] := 1;
  52. ti := 1;
  53. total := 1;
  54. while true do
  55. begin
  56. for i := ti downto 1 do
  57. begin
  58. w := ills[i];
  59. ills[i] := ills[ti];
  60. dec(ti);
  61. for j := 1 to linker[w]^[0] do
  62. begin
  63. a := linker[w]^[j];
  64. if ill[a] = 0 then
  65. begin
  66. ill[a] := 1;
  67. inc(ti);
  68. ills[ti] := a;
  69. end;
  70. end;
  71. end;
  72. if ti <= 0 then break;
  73. w := random(ti) + 1;
  74. ills[w] := ills[ti];
  75. dec(ti);
  76. inc(total, ti);
  77. if total >= ans then break;
  78. end;
  79. if total < ans then ans := total;
  80. end;
  81. end;
  82. procedure print;
  83. begin
  84. assign(output, ouf); rewrite(output);
  85. writeln(ans);
  86. close(output);
  87. end;
  88. begin
  89. prepare;
  90. init;
  91. main;
  92. print;
  93. end.