Page 2 I found the problem statement a little hard to understand, and I want to make some clarifications for anyone who is having difficulties. 1. We are looking for the maximum number of cycles such that each of these chosen cycles has at least one edge which is not included in any other chosen cycle. 2. The graph is not necessarily connected. I originally thought that we had to choose the maximum number of cycles which have at least one edge not included in all other chosen cycles. Hope this can help people. One of my AC solutions will crash on test 200 3 1 200 200 199 199 1 and on many other like this one. (I'm never using vertex #200 in this solution) I got WA1 so I made some debug and discovered that test 1 has N = 136 (with lines like if (N == 136) while(1); The problem with code was that I was using char instead of unsigned char :) Check this test: 136 6 130 132 136 135 135 130 130 133 133 134 133 135 One good answer should be 1 3 130 133 135 Won't help 4 5 1 2 2 3 3 4 4 1 2 4 My wa #1: 3 4 1 2 3 4 3 2 1 4 3 4 3 2 Each of these T tours has at least a road that does not belong to (T−1) other tours. Edited by author 16.03.2012 04:22 Edited by author 17.03.2012 02:34 Edited by author 17.03.2012 02:35My answer for the sample is 3 3 1 4 2 3 2 3 4 4 1 3 4 2 or 3 3 1 4 2 4 1 3 4 2 3 2 3 4 Can anyone give me the 1st test? why WA2?? program ural; var n,a,b,y:byte; m,i,z,r:integer; h,g:array[1..200]of integer; t:array[1..32767]of byte; l:array[1..32767]of integer; p,q:array[1..32767]of boolean; s:array[1..200]of byte; k:array[1..400]of integer; o:array[1..400]of byte; u:array[1..200]of boolean; x:boolean; procedure search(d:byte); var r:integer; begin u[d]:=true; r:=h[d]; while r<>0 do begin if u[t[r]]=false then begin inc(y); k[y]:=g[d]; g[d]:=y; o[y]:=t[r]; inc(y); k[y]:=g[t[r]]; g[t[r]]:=y; o[y]:=d; p[r]:=true; if q[r] then p[r+1]:=true else p[r-1]:=true; search(t[r]); end; r:=l[r]; end; end; procedure track(v,d:byte); var r:byte; begin if d=i then begin write(v,' '); for r:=1 to v-1 do write(s[r],' '); writeln(d); x:=true; exit; end; u[d]:=true; s[v]:=d; r:=g[d]; while r<>0 do begin if u[o[r]]=false then track(v+1,o[r]); if x then exit; r:=k[r]; end; end; begin assign(input,'travel.in'); assign(output,'travel.out'); reset(input); rewrite(output); readln(n,m); for i:=1 to m do begin readln(a,b); inc(r); l[r]:=h[a]; h[a]:=r; t[r]:=b; q[r]:=true; inc(r); l[r]:=h[b]; h[b]:=r; t[r]:=a; end; z:=m-n; for i:=1 to n do if u[i]=false then begin inc(z); search(i); end; if z<=0 then begin writeln(0); exit; end else writeln(z); for i:=1 to n do begin r:=h[i]; while r<>0 do begin if(q[r])and(p[r]=false)then begin x:=false; fillchar(u,sizeof(u),false); track(1,t[r]); end; r:=l[r]; end; end; end. I have no idea what's wrong... I am using DFS (something like euler-cycle detection); checking for self-loop edges; output format is right, tho it returns little bit different for sample test: 3 3 1 2 4 4 1 2 4 3 3 2 4 3 Please, any ideas about wa#1? oh, i forgot to add that i am doing dfs for every connected component separately! Edited by author 15.06.2010 03:05 anyone please? I did that too,my answer is completely the same as yours,and I WA on the 1st test too 3 3 4 1 2 3 3 1 2 3 4 1 3 My friend,I got AC. Maybe you should find connected components at first I wrote this program and think this is right. But I have WA#7. I tested my program by many my own test. And it gives correct answer in 100% cases. May be someone can give me a test. This is my prog: [Code deleted by author] Edited by author 28.08.2007 22:14 I'm still waiting for your help... My friend, you should be more attentive)) 200 * 200 is much more bigger then 5000)) And please delete your AC code)) Edited by author 28.08.2007 22:43 let N be the node num of the graph. so why the maximum cycle number is M-N+1? where M is the edge num. please... o, sorry, I made a mistake... is ur problem solved The correct formula is M-N+K, where K is the number of connected components of given graph. Why is not the question, if you know algo of building all these cycles... Edited by author 13.10.2022 15:00 Edited by author 13.10.2022 15:00 Does every tour always passes through the first city? There said, that it starts and ends in T1. Every tour in sample starts and ends in 1st vertice. So T1 = 1 or not? No. T1 is not always equal to 1. Why so simple problem have so small percent of accepted??? Is there bad test? Or there is some nasty trick? Here is my code: var a : array [1..200,1..200] of byte; b,u,now : array [1..200] of boolean; p,c : array [1..200] of byte; v,i,j,n,m,x,y,t,r,k : longint; procedure vvod; begin read(n,m); for i := 1 to m do begin read(x,y); a[x,y] := 1; a[y,x] := 1; end; x := 0; fillchar(b,sizeof(b),true); fillchar(now,sizeof(now),true); end; procedure dfs(x : byte); var i : byte; begin now[x] := false; for i := 1 to n do if now[i] and (a[x,i] = 1) then begin p[i] := x; dfs(i); end; end; procedure cycle; begin inc(t); k := 0; fillchar(u,sizeof(u),true); x := i; while (x <> 0) do begin u[x] := false; x := p[x]; end; x := j; while (x <> 0) do begin inc(k); c[k] := x; if not(u[x]) then begin break; r := k; end; u[x] := false; x := p[x]; end; y := i; while (y <> 0) and (y <> x) do begin inc(k); c[k] := x; x := p[x]; end; end; procedure find; begin for v := 1 to n do if now[v] then begin dfs(v); inc(x); end; writeln(m-n+x); for v := 1 to n do if b[v] then begin fillchar(now,sizeof(now),true); dfs(v); for i := 1 to n-1 do for j := i+1 to n do if not((p[i] = j) or (p[j] = i)) then begin if (a[i,j] = 1) and not(now[i]) and not(now[j]) then begin cycle; write(k); for x := 1 to r do write(' ',c[x]); for x := k downto r+1 do write(' ',c[x]); writeln; end; end; for i := 1 to n do if not(now[i]) then b[i] := false; end; end; begin vvod; find; end. 3 3 1 2 2 2 3 1 Your program outputs: 1 It is NOT right, but I'm not sure that input is correct :) Anybody who have got AC - how did you manage with it ??? Please, give me an interecting test! My new code (nothing new - only check for edges (x - x) : var a : array [1..200,1..200] of byte; b,u,now : array [1..200] of boolean; p,c : array [1..200] of byte; v,i,j,n,m,x,y,t,r,k : longint; procedure vvod; begin read(n,m); for i := 1 to m do begin read(x,y); if (x <> y) then begin a[x,y] := 1; a[y,x] := 1; end else inc(k); end; x := 0; fillchar(b,sizeof(b),true); fillchar(now,sizeof(now),true); end; procedure dfs(x : byte); var i : byte; begin now[x] := false; for i := 1 to n do if now[i] and (a[x,i] = 1) then begin p[i] := x; dfs(i); end; end; procedure cycle; begin inc(t); k := 0; fillchar(u,sizeof(u),true); x := i; while (x <> 0) do begin u[x] := false; x := p[x]; end; x := j; while (x <> 0) do begin inc(k); c[k] := x; if not(u[x]) then begin break; r := k; end; u[x] := false; x := p[x]; end; y := i; while (y <> 0) and (y <> x) do begin inc(k); c[k] := x; x := p[x]; end; end; procedure find; begin for v := 1 to n do if now[v] then begin dfs(v); inc(x); end; writeln(m-n+x-k); for v := 1 to n do if b[v] then begin fillchar(now,sizeof(now),true); dfs(v); for i := 1 to n-1 do for j := i+1 to n do if not((p[i] = j) or (p[j] = i)) then begin if (a[i,j] = 1) and not(now[i]) and not(now[j]) then begin cycle; write(k); for x := 1 to r do write(' ',c[x]); for x := k downto r+1 do write(' ',c[x]); writeln; end; end; for i := 1 to n do if not(now[i]) then b[i] := false; end; end; begin vvod; find; end. My prog have failed on a test like this : 9 10 1 2 1 3 2 3 4 5 4 6 5 6 7 8 7 9 8 9 1 9 How stupid mistake I made!!! But now I have AC =) Edited by author 24.10.2004 08:18 Edited by author 24.10.2004 08:19 9 12 9 4 4 8 8 7 7 9 9 5 5 2 2 6 6 8 4 3 3 2 2 1 1 7 here four cycles 5 8 1 2 2 3 3 4 1 4 2 5 5 4 1 5 5 3 also four cycles my result is 3 3 1 2 4 4 1 2 4 3 3 2 4 3 with distinct roads 4 1 3 1 3 2 why wa? did i understand something wrong? Edited by author 13.05.2004 20:15 bai Marius, da-mi si mie id-ul tau pe Yahoo MSN si mailul pe Hotmail sa te pun in lista, poate mai vorbim mailul meu e: ste_fanus@k.ro, ste_fanus@hotmail.com si pe yahoo e morbidel108 CODE IS HERE; #include "stdio.h" #include "string.h" long a[401][401]; long n,h,t; long i,j,m; int c[500]; int p[500]; long count=0; void bfs(int i) { int k; for(k=1;k<=n;k++) { if(c[k]==0) { if(a[i][k]==1) { a[i][k]=0; a[k][i]=0; c[k]=1; p[k]=i; bfs(k); } } } } void path(int a1,int a2) { int q[500]; int i=0; while(1) { q[i]=a2; i++; a2=p[a2]; if(a2==a1) break; } printf("%d",i+1); printf(" %d",a1); while(i>0) { printf(" %d",q[i-1]); i--; } printf("\n");
}
void main() { for(i=0;i<401;i++) for(j=0;j<401;j++) a[i][j]=0; scanf("%ld %ld",&n,&m); for(i=0;i<m;i++) { scanf("%ld %ld",&h,&t); a[h][t]=1; a[t][h]=1; } for(i=1;i<=n;i++) c[i]=0;
c[1]=1; bfs(1);
for(i=1;i<n;i++) { for(j=i+1;j<=n;j++) if(a[i][j]==1) { count++; } } printf("%ld\n",count); for(i=1;i<n;i++) { for(j=i+1;j<=n;j++) if(a[i][j]==1) { path(i,j); } }
} I have same problem and increased answer's array. got AC My solution is : #include <stdio.h> #define MAX 205 #define INF 2000000000 int n,m; int nasl[MAX][MAX]; int brn[MAX]; int vis[MAX]; int par[MAX]; int tree[MAX][MAX]; //short used[MAX][MAX]; int matr[MAX][MAX]; int brc; //short cycles[MAX*MAX][3]; // nachalo, kraj, naj-malko izpolzvanoto rebro int from,toFind; int count; int bri,bri2; int li[MAX*MAX],li2[MAX*MAX]; void DFS(int num) { int i; vis[num] = 1; for(i=0;i<brn[num];i++) { if(!vis[nasl[num][i]]) { tree[num][nasl[num][i]] = 1; tree[nasl[num][i]][num] = 1; par[nasl[num][i]] = num; DFS(nasl[num][i]); } } } void DFSW() { int i; for(i=0;i<n;i++) if(!vis[i]) { par[i] = -1; DFS(i); } } int main() { int i,i2,i3,cur; int a1,a2; // freopen("1077.in","r",stdin); scanf("%d %d",&n,&m); for(i=0;i<=n;i++) { vis[i] = 0; brn[i] = 0; for(i2=0;i2<n;i2++) { tree[i][i2] = 0; } } for(i=0;i<m;i++) { scanf("%d %d",&a1,&a2); nasl[a1-1][brn[a1-1]++] = a2-1; nasl[a2-1][brn[a2-1]++] = a1-1; matr[a1-1][a2-1] = matr[a2-1][a1-1] = 1; } DFSW(); // DFS(0); count = 0; for(i=0;i<n;i++) for(i2=i+1;i2<n;i2++) if(matr[i][i2]==1 && tree[i][i2]==0) count++; printf("%d\n",count); for(i=0;i<n;i++) for(i2=i+1;i2<n;i2++) if(matr[i][i2]==1 && tree[i][i2]==0) { bri = 0; bri2 = 0; cur = i; while(cur!=-1) { li[bri++] = cur; cur = par[cur]; } cur = i2; while(cur!=-1) { li2[bri2++] = cur; cur = par[cur]; } bri--; bri2--; while(li[bri]==li2[bri2]) { bri--; bri2--; } printf("%d ",bri+2+bri2+1); for(i3=0;i3<=bri+1;i3++) printf("%d ",li[i3]+1); for(i3=bri2;i3>=0;i3--) printf("%d ",li2[i3]+1); printf("\n"); } return 0; } CONST NMax = 250; VAR Route : ARRAY[1..NMax, 1..NMax] OF LongInt; Used : ARRAY[1..NMax] OF Boolean; Path : ARRAY[0..NMax] OF Integer; N, M, I, T, H, Count : LongInt; Found : Boolean; PROCEDURE DSF(Start, C : LongInt); VAR I : LongInt; BEGIN Used[C] := True; IF (Route[C, Start] = 2) THEN BEGIN Found := True; Used[C] := False; Exit; END; FOR I := 1 TO N DO IF (NOT Used[I]) AND (Route[C, I] = 2) THEN BEGIN Route[C, I] := 0; Route[I, C] := 0; DSF(Start, I); Route[C, I] := 2; Route[I, C] := 2; IF Found THEN Break; END; IF (NOT Found) THEN IF (Route[C, Start] = 1) THEN BEGIN Route[Start, C] := 2; Route[C, Start] := 2; Found := True; END; IF NOT Found THEN FOR I := 1 TO N DO IF (NOT Used[I]) AND (Route[C, I] = 1) THEN BEGIN Route[C, I] := 0; Route[I, C] := 0; DSF(Start, I); IF Found THEN BEGIN Route[C, I] := 2; Route[I, C] := 2; Break; END ELSE BEGIN Route[C, I] := 1; Route[I, C] := 1; END; END; Used[C] := False; END; PROCEDURE DSF2(Start, C, Size : LongInt); VAR I : LongInt; BEGIN Used[C] := True; IF (Route[C, Start] = 1) THEN BEGIN Found := True; Used[C] := False; Path[Size] := C; Path[0] := Size; Exit; END; FOR I := 1 TO N DO IF (NOT Used[I]) AND (Route[C, I] = 1) THEN BEGIN Route[C, I] := 0; Route[I, C] := 0; DSF2(Start, I, Size+1); Route[C, I] := 1; Route[I, C] := 1; IF Found THEN BEGIN Path[Size] := C; Break; END; END; IF (NOT Found) THEN IF (Route[C, Start] = 2) THEN BEGIN Route[Start, C] := 1; Route[C, Start] := 1; Path[Size] := C; Path[0] := Size; Found := True; END; IF NOT Found THEN FOR I := 1 TO N DO IF (NOT Used[I]) AND (Route[C, I] = 2) THEN BEGIN Route[C, I] := 0; Route[I, C] := 0; DSF2(Start, I, Size+1); IF Found THEN BEGIN Route[C, I] := 1; Route[I, C] := 1; Path[Size] := C; Break; END ELSE BEGIN Route[C, I] := 2; Route[I, C] := 2; END; END; Used[C] := False; END; BEGIN FillChar(Route, SizeOf(Route), 0); FillChar(Used, SizeOf(Used), False); ReadLn(N, M); FOR I := 1 TO M DO BEGIN ReadLn(T, H); Route[T, H] := 1; Route[H, T] := 1; END; Count := 0; FOR T := 1 TO N DO FOR H := 1 TO N DO IF Route[T, H] = 1 THEN BEGIN Used[T] := True; Route[T, H] := 0; Route[H, T] := 0; Found := False; DSF(T, H); IF Found THEN BEGIN Route[T, H] := 2; Route[H, T] := 2; Inc(Count); END ELSE BEGIN Route[T, H] := 1; Route[H, T] := 1; END; Used[T] := False; END; WriteLn(Count); IF Count <> 0 THEN BEGIN FOR T := 1 TO N DO FOR H := 1 TO N DO IF Route[T, H] = 2 THEN BEGIN Used[T] := True; Route[T, H] := 0; Route[H, T] := 0; Found := False;
I think my method is right, but it always gets WR! Thank u! #include "stdio.h" int n, m, M[201][201]; int B[201][2], F[201]; void Init() { int i, j, k;
scanf("%d %d",&n,&m); for (i=1; i<=n; i++) for (j=1; j<=n; j++) M[i][j] = 0; for (k=0; k<m; k++) { scanf("%d %d",&i,&j); if (i!=j) M[i][j] = M[j][i] = 1; } } void CT(int num, int father, int level) { int i; F[num] = 1; B[num][0] = father; B[num][1] = level; for (i=1; i<=n; i++) if (!F[i] && M[num][i]) { M[num][i] = M[i][num] = 0; CT(i, num, level+1); } } void CreateTree() { int i;
for (i=1; i<=n; i++) F[i] = 0; /* for (i=1; i<=n; i++) if (!F[i]) { Pth[0] = i; nail = head = 0; B[i][0] = 0; B[i][1] = 1; F[i] = 1; while (head<=nail) { j = Pth[head]; head++; for (k=1; k<=n; k++) if (!F[k] && M[j][k]) { nail++; Pth[nail] = k; B[k][0] = j; B[k][1] = B[j][1] + 1; F[k] = 1; M[j][k] = M[k][j] = 0; } } }*/ for (i=1; i<=n; i++) { if (!F[i]) CT(i, 0, 1); } /* for (i=1; i<=n; i++) printf("%d %d\n",B[i][0],B[i][1]);*/ } void Caculate() { int total, i, j; int Pth[2][201], l[2]; for (i=1, total=0; i<=n; i++) for (j=1; j<=n; j++) if (M[i][j]==1) { total++; M[i][j] = M[j][i] = 2; } printf("%d\n",total); for (i=1; i<=n; i++) for (j=1; j<=n; j++) if (M[i][j]==2) { M[i][j] = M[j][i] = 0; l[0] = l[1] = 0; Pth[0][0] = i; Pth[1][0] = j;
while (Pth[0][l[0]]!=Pth[1][l[1]]) if (B[Pth[0][l[0]]][1]==B[Pth [1][l[1]]][1]) { l[0]++; Pth[0][l[0]] = B[Pth[0][l[0]-1]][0]; l[1]++; Pth[1][l[1]] = B[Pth[1][l[1]-1]][0]; } else if (B[Pth[0][l[0]]][1]>B [Pth[1][l[1]]][1]) { l[0]++; Pth[0][l[0]] = B[Pth[0][l[0]-1]][0]; } else { l[1]++; Pth[1][l[1]] = B[Pth[1][l[1]-1]][0]; } printf("%d",l[0]+l[1]+1); for (i=0; i<=l[0]; i++) printf(" % d",Pth[0][i]); for (i=l[1]-1; i>=0; i--) printf(" % d",Pth[1][i]); printf("\n"); } } main() { Init(); CreateTree(); Caculate(); } The reason is not Wrong answer as you can think. I use recursion in my solution of this problem and get mem limit exceeded (it is stack overflow); at all test cases, that I could make, my program works successfull and I do not know what the matter. Please - if you have any test cases - post it to this webboard or to my email pflojd@yandex.ru. Page 1 #include<stdio.h> #include<memory.h> int map[200][200],mark[200],m,n; void make(int v){ int i; for (i=0;i<n;i++) if (mark[i]==0 && map[v][i]>0) { mark[i]=v+1; map[v][i]=-map[v][i]; map[i][v]=-map[i][v]; make(i); } } void main(){ int i,j,aa,bb,la,lb,a[200],b[200],count,k; scanf("%d%d",&n,&m); memset(map,0,sizeof map); for (i=0;i<m;i++) { scanf("%d%d",&aa,&bb); map[aa-1][bb-1]=map[bb-1][aa-1]=1; } memset(mark,0,sizeof mark); i=0; do{ while (i<n && mark[i]) i++; if (i==n) break; mark[i]=32767; make(i); }while (1); count=0; for (i=0;i<n;i++) for (j=i+1;j<n;j++) if (map[i][j]>0) count++; printf("%d\n",count); for (i=0;i<n;i++) for (j=i+1;j<n;j++) if (map[i][j]>0) { la=0; aa=i; do{ a[la++]=aa; if (mark[aa]==32767) break; aa=mark[aa]-1; }while (1); lb=0; bb=j; do{ b[lb++]=bb; if (mark[bb]==32767) break; bb=mark[bb]-1; }while(1);
while (a[la-1]==b[lb-1]) {la--;lb--;} printf("%d ",la+lb+1); for (k=0;k<la+1;k++) printf("%d ",a[k]+1); for (k=lb-1;k>=0;k--) printf("%d ",b[k] +1); printf("\n"); } } > #include<stdio.h> > #include<memory.h> > int map[200][200],mark[200],m,n; > void make(int v){ > int i; > for (i=0;i<n;i++) > if (mark[i]==0 && map[v][i]>0) { > mark[i]=v+1; > map[v][i]=-map[v][i]; > map[i][v]=-map[i][v]; > make(i); > } > } > void main(){ > int i,j,aa,bb,la,lb,a[200],b[200],count,k; > scanf("%d%d",&n,&m); > memset(map,0,sizeof map); > for (i=0;i<m;i++) { > scanf("%d%d",&aa,&bb); > map[aa-1][bb-1]=map[bb-1][aa-1]=1; > } > memset(mark,0,sizeof mark); > i=0; > do{ > while (i<n && mark[i]) i++; > if (i==n) break; > mark[i]=32767; > make(i); > }while (1); > count=0; > for (i=0;i<n;i++) > for (j=i+1;j<n;j++) if (map[i][j]>0) count++; > printf("%d\n",count); > for (i=0;i<n;i++) > for (j=i+1;j<n;j++) > if (map[i][j]>0) { > la=0; > aa=i; > do{ > a[la++]=aa; > if (mark[aa]==32767) break; > aa=mark[aa]-1; > }while (1); > lb=0; > bb=j; > do{ > b[lb++]=bb; > if (mark[bb]==32767) break; > bb=mark[bb]-1; > }while(1); > > while (a[la-1]==b[lb-1]) {la--;lb--;} > printf("%d ",la+lb+1); > for (k=0;k<la+1;k++) printf("%d ",a[k]+1); > for (k=lb-1;k>=0;k--) printf("%d ",b[k] > +1); > printf("\n"); > } > } |
|