ural1099_5_10.dpr 1.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103
  1. {$M 6400000}
  2. program ural1099_5_10;
  3. const maxn=300;
  4. randtime=5;
  5. tttime=10;
  6. var n,ans:longint;
  7. p,q,my,ansy:array[1..maxn]of longint;
  8. map:array[1..maxn,1..maxn]of boolean;
  9. u:array[1..maxn]of boolean;
  10. procedure swap(var x,y:longint);
  11. var t:longint;
  12. begin
  13. t:=x;x:=y;y:=t;
  14. end;
  15. procedure inputint;
  16. var a,b:longint;
  17. begin
  18. readln(n);
  19. while not(eof) do
  20. begin
  21. readln(a,b);
  22. map[a,b]:=true;
  23. map[b,a]:=true;
  24. end;
  25. end;
  26. function aug(x:longint):boolean;
  27. var i:longint;
  28. begin
  29. u[x]:=true;
  30. for i:=1 to n do
  31. if not(u[q[i]]) then
  32. if map[x,q[i]] then
  33. begin
  34. u[q[i]]:=true;
  35. if (my[q[i]]=0)or(aug(my[q[i]])) then
  36. begin
  37. my[q[i]]:=x;
  38. my[x]:=q[i];
  39. aug:=true;
  40. exit;
  41. end;
  42. end;
  43. aug:=false;
  44. end;
  45. procedure updata(tmp:longint);
  46. var i:longint;
  47. begin
  48. ans:=tmp;
  49. for i:=1 to n do ansy[i]:=my[i];
  50. end;
  51. procedure workans;
  52. var i,tmp,j,k,ttt:longint;
  53. begin
  54. fillchar(my,sizeof(my),0);
  55. tmp:=0;
  56. for i:=1 to n do
  57. if my[p[i]]=0 then
  58. for ttt:=1 to tttime do
  59. begin
  60. fillchar(u,sizeof(u),0);
  61. if aug(p[i]) then begin inc(tmp);break end
  62. else
  63. for j:=1 to n do
  64. begin
  65. k:=j+random(n-j+1);
  66. swap(q[j],q[k]);
  67. end;
  68. end;
  69. if tmp>ans then updata(tmp);
  70. end;
  71. procedure work;
  72. var i,j,time:longint;
  73. begin
  74. for i:=1 to n do
  75. begin
  76. p[i]:=i;
  77. q[i]:=i;
  78. end;
  79. for time:=1 to randtime do
  80. begin
  81. for i:=1 to n do
  82. begin
  83. j:=i+random(n-i+1);
  84. swap(q[i],q[j]);
  85. j:=i+random(n-i+1);
  86. swap(p[i],p[j]);
  87. end;
  88. workans;
  89. end;
  90. end;
  91. procedure outputint;
  92. var i:longint;
  93. begin
  94. writeln(ans*2);
  95. for i:=1 to n do
  96. if ansy[i]>i then writeln(i,' ',ansy[i]);
  97. end;
  98. begin
  99. randomize;
  100. inputint;
  101. work;
  102. outputint;
  103. end.