Discussion @ 1077. Travelling Tours @ Timus Online Judge

Please, give me any hint to solve this problem! Nazarov Denis (nsc2001@rambler.ru) 3 Feb 2002 18:08

Re: Please, give me any hint to solve this problem! Tran Nam Trung (trungduck@yahoo.com) 3 Feb 2002 19:49

Just use DFS !
Good luck !
>

I use greedy method+DFS but get WA! Please,give me some tests. (+) Nazarov Denis (nsc2001@rambler.ru) 4 Feb 2002 09:11

My program:

Program t1077;

Const MaxN=200;

Var   G,GT        : array[1..MaxN,1..MaxN]of byte;
      T,Use       : array[1..MaxN]of byte;
      N,M,i,a1,a2 : integer;
      Ans,count   : integer;
      di,dj       : integer;
      w           : boolean;

Procedure Rec(cur,first : integer);
Var i : integer;
begin
count:=count+1;
T[count]:=cur;
if G[cur,first]=1 then begin
     ans:=ans+1;
     di:=t[1];
     dj:=t[count];
     g[di,dj]:=2;
     g[dj,di]:=2;
     if w then begin
      write(count);
      for i:=1 to count do write(' ',t[i]);
      writeln;
     end;
    end;
for i:=first+1 to N do if use[i]=0 then
   if G[cur,i]=1 then begin
    use[i]:=1;
    G[cur,i]:=0;
    G[i,cur]:=0;
    Rec(i,first);
    if G[cur,i]=0 then G[cur,i]:=1;
    if G[i,cur]=0 then G[i,cur]:=1;
   end;
count:=count-1;
end;

begin
fillchar(G,sizeof(G),0);
Read(N,M);
for i:=1 to M do begin
   read(a1,a2);
   G[a1,a2]:=1;
   G[a2,a1]:=1;
end;
GT:=G;
Ans:=0;
w:=false;
for i:=1 to N-2 do begin
   count:=0;
   fillchar(use,sizeof(use),0);
   rec(i,i);
end;
writeln(ans);
G:=GT;
w:=true;
Ans:=0;
for i:=1 to N-2 do begin
   count:=0;
   fillchar(use,sizeof(use),0);
   rec(i,i);
end;
end.

Re: I use greedy method+DFS but get WA! Please,give me some tests. (+) Tran Nam Trung (trungduck@yahoo.com) 4 Feb 2002 10:48

> My program:
>
> Program t1077;
>
> Const MaxN=200;
>
> Var   G,GT        : array[1..MaxN,1..MaxN]of byte;
>       T,Use       : array[1..MaxN]of byte;
>       N,M,i,a1,a2 : integer;
>       Ans,count   : integer;
>       di,dj       : integer;
>       w           : boolean;
>
> Procedure Rec(cur,first : integer);
> Var i : integer;
> begin
>   count:=count+1;
>   T[count]:=cur;
>   if G[cur,first]=1 then begin
>      ans:=ans+1;
>      di:=t[1];
>      dj:=t[count];
>      g[di,dj]:=2;
>      g[dj,di]:=2;
>      if w then begin
>       write(count);
>       for i:=1 to count do write(' ',t[i]);
>       writeln;
>      end;
>     end;
>   for i:=first+1 to N do if use[i]=0 then
>    if G[cur,i]=1 then begin
>     use[i]:=1;
>     G[cur,i]:=0;
>     G[i,cur]:=0;
>     Rec(i,first);
>     if G[cur,i]=0 then G[cur,i]:=1;
>     if G[i,cur]=0 then G[i,cur]:=1;
>    end;
>   count:=count-1;
> end;
>
> begin
> fillchar(G,sizeof(G),0);
> Read(N,M);
> for i:=1 to M do begin
>    read(a1,a2);
>    G[a1,a2]:=1;
>    G[a2,a1]:=1;
>   end;
> GT:=G;
> Ans:=0;
> w:=false;
> for i:=1 to N-2 do begin
>    count:=0;
>    fillchar(use,sizeof(use),0);
>    rec(i,i);
>   end;
> writeln(ans);
> G:=GT;
> w:=true;
> Ans:=0;
> for i:=1 to N-2 do begin
>    count:=0;
>    fillchar(use,sizeof(use),0);
>    rec(i,i);
>   end;
> end.
Well, I have ran your program for my test cases, and it got WA. Your
number of tours is correct but your routes is wrong because one route
doesn't have any road that diffrent from others route. Sorry that I
can't post that test case here because it's too large. Check your
program again. Good luck !

Thank you! I find some errors and chaged my code but I still get WA. Please, recheck my program!(+) Nazarov Denis (nsc2001@rambler.ru) 4 Feb 2002 13:46

My program:

Program t1077;

Const MaxN = 200;

Type Path = record
       P : array[1..MaxN]of byte;
       l : byte;
      end;

Var   G           : array[1..MaxN,1..MaxN]of byte;
      Use,P       : array[1..MaxN]of byte;
      N,M,i,a1,a2 : integer;
      Ans,count,j : integer;

Procedure Rec(cur : integer);
Var i : integer;
begin
for i:=1 to N do if use[i]=0 then
   if G[cur,i]=1 then begin
    use[i]:=1;
    G[cur,i]:=0;
    G[i,cur]:=0;
    P[i]:=cur;
    Rec(i);
   end;
end;

Procedure MakePath(Num : integer; Var X : Path);
Var len,next : integer;
begin
len:=0;
next:=num;
while next>=1 do begin
   len:=len+1;
   x.p[len]:=next;
   next:=p[next];
end;
x.l:=len;
end;

Procedure WritePath(e1,e2 : integer);
Var c1,c2,i : integer;
    p1,p2   : Path;
begin
MakePath(e1,p1);
MakePath(e2,p2);
c1:=p1.l;
c2:=p2.l;
while (p1.p[c1]=p2.p[c2]) do begin
    c1:=c1-1;
    c2:=c2-1;
   end;
write(c1+c2+1);
for i:=1 to c1+1 do write(' ',p1.p[i]);
for i:=c2 downto 1 do write(' ',p2.p[i]);
writeln;
end;

begin
fillchar(G,sizeof(G),0);
Read(N,M);
for i:=1 to M do begin
   read(a1,a2);
   G[a1,a2]:=1;
   G[a2,a1]:=1;
end;
fillchar(Use,SizeOf(Use),0);
Use[1]:=1;
Rec(1);
Ans:=0;
for i:=1 to N-1 do
for j:=i+1 to N do
   if G[i,j]=1 then
    Ans:=Ans+1;
Writeln(Ans);
for i:=1 to N-1 do
for j:=i+1 to N do
   if G[i,j]=1 then
    WritePath(i,j);
end.

Oh sorry! What a fool error! I get AC! Thank you ! ! ! Nazarov Denis (nsc2001@rambler.ru) 4 Feb 2002 14:20

> My program:
>
> Program t1077;
>
> Const MaxN = 200;
>
> Type Path = record
>        P : array[1..MaxN]of byte;
>        l : byte;
>       end;
>
> Var   G           : array[1..MaxN,1..MaxN]of byte;
>       Use,P       : array[1..MaxN]of byte;
>       N,M,i,a1,a2 : integer;
>       Ans,count,j : integer;
>
> Procedure Rec(cur : integer);
> Var i : integer;
> begin
>   for i:=1 to N do if use[i]=0 then
>    if G[cur,i]=1 then begin
>     use[i]:=1;
>     G[cur,i]:=0;
>     G[i,cur]:=0;
>     P[i]:=cur;
>     Rec(i);
>    end;
> end;
>
> Procedure MakePath(Num : integer; Var X : Path);
> Var len,next : integer;
> begin
>   len:=0;
>   next:=num;
>   while next>=1 do begin
>    len:=len+1;
>    x.p[len]:=next;
>    next:=p[next];
>   end;
>   x.l:=len;
> end;
>
> Procedure WritePath(e1,e2 : integer);
> Var c1,c2,i : integer;
>     p1,p2   : Path;
> begin
>   MakePath(e1,p1);
>   MakePath(e2,p2);
>   c1:=p1.l;
>   c2:=p2.l;
>   while (p1.p[c1]=p2.p[c2]) do begin
>     c1:=c1-1;
>     c2:=c2-1;
>    end;
>   write(c1+c2+1);
>   for i:=1 to c1+1 do write(' ',p1.p[i]);
>   for i:=c2 downto 1 do write(' ',p2.p[i]);
>   writeln;
> end;
>
> begin
> fillchar(G,sizeof(G),0);
> Read(N,M);
> for i:=1 to M do begin
>    read(a1,a2);
>    G[a1,a2]:=1;
>    G[a2,a1]:=1;
>   end;
> fillchar(Use,SizeOf(Use),0);
> Use[1]:=1;
> Rec(1);
> Ans:=0;
> for i:=1 to N-1 do
>   for j:=i+1 to N do
>    if G[i,j]=1 then
>     Ans:=Ans+1;
> Writeln(Ans);
> for i:=1 to N-1 do
>   for j:=i+1 to N do
>    if G[i,j]=1 then
>     WritePath(i,j);
> end.

Discussion of Problem 1077. Travelling Tours