ural1099_10.dpr 1.6 KB

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