Advertisement
Guest User

Untitled

a guest
Nov 17th, 2012
1,387
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Pascal 1.82 KB | None | 0 0
  1. ------------------------------------------------------------------------------------------------------------
  2.  
  3. В области L находится n городов. Некоторые пары городов соединены проселочной дорогой с двусторонним движением. Начавшись в каком-то городе дорога не может заканчиваться в нем же. В этом году состояние дорог позволило отделение ГИБДД области L провести гонки под лозунгом "скажи НЕТ нарушениям скоростного режима". Было решено, что круговая трасса должна стоять из четырех дорог, но не  может два раза проходить через один и тот же город. Организаторы уже приступили к составлению отчёта и для этого им требуется количество различных трасс.
  4.  
  5.  
  6. rally.in
  7. 4 6
  8. 1 2
  9. 2 3
  10. 3 4
  11. 4 1
  12. 1 3
  13. 2 4
  14.  
  15. rally.out
  16. 3
  17. ------------------------------------------------------------------------------------------------------------
  18.  
  19.  
  20.  
  21. type myset = set of longint;
  22. var n,m,i,x,y,res:longint;a:array[0..300,0..300]  of boolean; b:set of myset;
  23.  
  24.  
  25.  
  26. procedure dfs(st,i,l:longint;trip:set of longint);
  27. begin
  28. var j:longint;
  29. if l=4 then  
  30.     if (st=i) and not(trip in b) then begin res:=res+1; b:=b+[trip] end
  31.   else
  32.     exit;
  33. for j:=1 to n do if a[i][j] and not(j in trip) then dfs(st,j,l+1,trip+[j]);
  34. end;
  35.  
  36. begin
  37. read(n,m);
  38. for i:=1 to m do
  39. begin
  40.   read(x, y);
  41.   a[x][y]:=true;
  42.   a[y][x]:=true;
  43. end;
  44.  
  45. {dfs(1,1,0,[]);}
  46. for i:=1 to n do dfs(i,i,0,[]);
  47. write(res);
  48. {write (res div 2)}
  49. end.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement