Please, give me any hint to solve this problem! Re: Please, give me any hint to solve this problem! Just use DFS !
Good luck !
> I use greedy method+DFS but get WA! Please,give me some tests. (+) 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. (+) > 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!(+) 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 ! ! ! > 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. |
