That's my q. Because the edges are directed Try this test 5 2 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 Edited by author 20.12.2015 17:14 i used Fleury algorithm to find a Euler cycle Edited by author 11.09.2015 12:47 Ridiculous! It's O(damn E)! AND I got rid of all the lists and used simple arrays instead. It just cannot get any faster than that... Input 4 2 0 0 1 0 0 0 1 0 1 1 0 1 0 0 1 0 Output 2 1 1 4 4 1 1 2 2 4 4 2 In C++ don't use cout and cin! Just use scanf(...) and printf(...). Enjoy! Edited by author 24.03.2012 00:22 Is my greedy algo correct? On each step I choose an edge to vertex with the greatest out-degree. I have WA 8. Of course, you should find Euler cycle If you code on Java use Thread to kill stack overflow This my AC program. If I change one cycle, I get WA#3. WHY???? import java.io.IOException; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Solution { public static int[][] a; public static int[] d; public static int n; public static int top; public static int[] bol; public static void dfs(int v){ bol[v] = 1; int i; for(i = 0;i < n;i ++){ if(a[v][i] == 1){ a[v][i] = 0; dfs(i); } } d[top] = v; top ++; } public static void solve()throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); m --; a = new int[n][n]; d = new int[n * n + 1]; bol = new int[n]; top = 0; int i, j; int res = 0; for(i = 0;i < n;i ++){ st = new StringTokenizer(in.readLine()); for(j = 0;j < n;j ++){ a[i][j] = 1 - Integer.parseInt(st.nextToken()); if(i == j)a[i][i] = 0; res += a[i][j]; } } dfs(m); for(i = top - 1;i > 0;i --){ System.out.println((d[i] + 1) + " " + (d[i - 1] + 1)); } } public static void main(String[] args){ new Thread(){ public void run(){ try{ solve(); }catch(Exception e){ } } }.start(); } } This cycle. for(i = top - 1;i > 0;i --){ System.out.println((d[i] + 1) + " " + (d[i - 1] + 1)); } change to: for(i = 0;i < top - 1;i ++){ System.out.println((d[i] + 1) + " " + (d[i + 1] + 1)); } had the same problem. Test #3. Bad: for (int i=0; i<ResultSize-1; ++i) printf("%d %d\n", Result[i]+1, Result[i+1]+1); Good: int i=ResultSize; while (i-->1) printf("%d %d\n", Result[i]+1, Result[i-1]+1); Changed bad to good and got AC. Admins, please check test #3. There is such sentence in the problem statement: "One can pass through the channel only in one direction". That means the adjacency matrix is not symmetric and when you output the answer in reverse order, you may cross some channels such that channel (i,j) exists but (j,i) does not. you cannot post code here!!!!! There was problem with this task, but now I get AC. Edited by author 27.03.2007 00:05 Edited by author 27.03.2007 00:36 How can this algo get Stack overflow(test 12)? #include <string> #include <vector> #include<iostream> #include<queue> using namespace std; struct Pair{ int a,b; }; vector<int> res; int n,s; int a[1111][1111]; void dfs(int ver){ for(int i=0;i<n;i++) if(ver!=i && !a[ver][i]){ a[ver][i]=1; dfs(i); } res.push_back(ver); } int main(){ cin>>n>>s; for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin>>a[i][j]; dfs(s-1); reverse(res.begin(),res.end()); for(int i=1;i<res.size();i++) cout<<res[i-1]+1<<" "<<res[i]+1<<endl; system("pause"); return 0; } Use #pragma comment(linker, "/STACK:16777216") if you got Wa 2 try it 4 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 without output if you got MLE12 Not foget use dispose. Gool Luck and Have fun. another hint: if you have wa3, try to inverse output. for example, your program writes 3 1 1 2 2 3 try 3 2 2 1 1 3 GL be simpler why ? Edited by author 28.06.2005 23:43 I usually design algo according to the memory limit... Maybe I should rewrite the pro which needs less memory and faster... To Dilyan: Years ago, Pascal's memory will add another 370K, that is to say, your pro uses 641 + 370 > 1000k... That is why I said it is harder to got AC in pascal, I have to make exchange between time and space. Edited by author 29.06.2005 08:31 I got WA on test 3. Here is my code: Program ex; Const Rule :Array [0..7] Of Integer =(1,2,4,8,16,32,64,128); Var G :Array [1..1001,0..125] Of Byte; Len,M :Integer; St,Ar :Array [1..32010] Of Integer; N,Be :Integer; Procedure Init; Var P,Q,U :Integer; Begin Readln(N,Be); For P:=1 To N Do For Q:=1 To N Do Begin Read(U); If (U=0) And (P<>Q) Then Inc(G[P,(Q-1) Div 8],Rule[(Q-1) Mod 8]); End; End; Procedure Main; Var I,J :Integer; Begin M:=0; Len:=1; St[1]:=Be; Repeat I:=St[Len]; J:=1; Repeat If G[I,(J-1) Div 8] And Rule[(J-1) Mod 8]>0 Then Break; Inc(J); Until J>N; If J<=N Then Begin Dec(G[I,(J-1) Div 8],Rule[(J-1) Mod 8]); Inc(Len); St[Len]:=J; End Else Begin Dec(Len); Inc(M); Ar[M]:=I; End; Until Len=0; If Ar[1]<>Be Then Begin Repeat Until False; End; For I:=1 To M-1 Do Writeln(Ar[I],' ',Ar[I+1]); End; Begin Init; Main; End. I can't find my mistake........ Who can give me some test........ This is my code : -------------------------------------------------------- const Maxn = 1010 ; var h : Array [0..Maxn,0..100] Of Integer ; l : Array [0..Maxn] Of Integer ; list : Array [0..66000] Of Integer ; len , n , first , x : LongInt ; procedure init ; var i , j , k : Integer ; begin read ( n , first ) ; for i := 1 to n do for j := 1 to n do begin read ( k ) ; if ( k = 0 ) and ( i <> j ) then begin Inc ( l[i] ) ; h[i,l[i]] := j ; end; end; end; procedure Dfs ( k : Integer ) ; begin While l[k] > 0 do begin Dec ( l[k] ) ; Dfs ( h[k,l[k]+1] ) ; end; Inc ( len ) ; list[len] := k ; end; procedure out ; var i : LongInt ; begin if n > 1 then begin write ( list[1] ) ; for i := 2 to len - 1 do begin writeln ( ' ' , list[i] ) ; write ( list[i] ) ; end; writeln ( ' ' , list[len] ) ; end; end; begin init ; Dfs ( first ) ; out ; end. I was getting WA3 until understood, that my program gives a wrong output on the following test: 3 2 0 0 1 1 0 0 0 1 0 To my mind, the only possible answer is as follows: 2 3 3 1 1 2 And my old solution output just the opposite, i.e. 2 1 1 3 3 2 Good luck (! rafailka. Edited by author 13.03.2005 10:02 For sample input: 4 2 0 0 1 0 0 0 1 0 1 1 0 1 0 0 1 0 I must find Eulerian cycle for such graph: 0 1 0 1 1 0 0 1 0 0 0 0 1 1 0 0 Is new graph correct or not? Edited by author 01.11.2004 21:34 What don't you like about it? I bet, it's OK(! rafailka. Edited by author 13.03.2005 09:56 var g:array[1..1000,1..1000] of Boolean; i,j,n,a,k,s:smallint; procedure find(i:smallint); var j:smallint; begin for j:=n downto 1 do if g[i,j] then begin g[i,j]:=false; find(j) end; if s<>0 then writeln(s,' ',i); s:=i; end; begin assign(input,''); reset(input); readln(n,a); for i:=1 to n do for j:=1 to n do begin read(k); g[i,j]:=(k=0) and (i<>j) end; close(input); s:=0; find(a); end. If I put s in memory and write it in reverse order I get MLE on test 12: var g:array[1..1000,1..1000] of Boolean; i,j,n,a,k,st:smallint; s:array[1..32000] of smallint; procedure find(i:smallint); var j:smallint; begin for j:=n downto 1 do if g[i][j] then begin g[i][j]:=false; find(j) end; inc(st); s[st]:=i end; begin assign(input,''); reset(input); readln(n,a); for i:=1 to n do for j:=1 to n do begin read(k); g[i][j]:=(k=0) and (i<>j) end; close(input); st:=0; find(a); for i:=st-1 downto 1 do writeln(s[i+1],' ',s[i]); end. Please help me solve either of this two problems. There are two way to accept it: 1. Use stack instead of recursion. 2. Use recursion without variable "j". In all cases you can use array "st" and don't worry about memory limit. you can use dynamic lists for the graph instead of that bool matrix... no tricks, just an Eulerian cycle on the negative edges... on the negative edges? Are there any differences with on the unnegative edags? you have the adjacency(?) matrix. Negative means that you change 1 with 0 and 0 with 1. Then, on this new graph you make an Eulerian cycle. I can post my source if really need I'm sorry I can't understand you. What does "change 1 with 0 and 0 with 1." mean? The problem gives you that binary matrix with a[i][j] = 1 if i and j are connected. Reversing 1 with 0 and vice-versa means that if i and j are connected than you unconnect them (i.e. a[i][j] = 0) and if they are not connected, a[i][j] = 0, you connect them, a[i][j] = 1. You do this because the spaceship can build cannals that don't exist, so it must walk only between unconnected nodes. Covering all cannals that do not exist and return to the initial node is a cycle that covers all these unconnected edges once, exactly like an Eulerian cycle. How did you pass the first tests if you didn't understand these? With all respect. Thank you! I mistook you at that time...Very sorry.. But I think I use the same method as you..Maybe there is something wrong with my code. #include <stdio.h> #include <stdlib.h> #define N 1050 #define setbit1(x,y) ( a[x][y >> 3] |= (1 << (y & 7)) ) #define setbit0(x,y) ( a[x][y >> 3] &= ~(1 << (y & 7)) ) #define getbit(x,y) ( a[x][y >> 3] & (1 << (y & 7)) ) int n, s, x, lev; int a[N][N/8], d[32010]; void read () { int i, j, v, x = 0; //freopen( "1176.in", "rt", stdin ); scanf( "%d%d", &n, &s ); for ( i = 1; i <= n; i++ ) for ( j = 1; j <= n; j++ ) { scanf( "%d", &v ); if ( !v && i != j ) setbit1( i, j ), x++; } if ( !x ) exit( 0 ); } void ciclu (int s) { int j; lev++; for ( j = 1; j <= n; j++ ) if ( getbit( s, j ) ) { setbit0( s, j ); ciclu( j ); } d[++d[0]] = s; /* if ( !x || lev == 1 ) printf( "%d ", s ); else printf( "%d\n%d ", s, s ); x = s; lev--;*/ } int main () { int i;
read(); ciclu( s ); for ( i = 1; i < d[0]; i++ ) printf( "%d %d\n", d[i], d[i + 1] ); return 0; } What is it DY-algo?:) May be you have some links about it? #include<iostream.h> int*conn[1001]; int*done[1001]; int quan[1001]; void razrul(int); int *tstr; void main(){ int str[1001]; tstr=new int[32200]; int i,j,n,q,a; cin >> n >> a; a--; for(i=0;i<n;i++) { for(j=0;j<n;j++) cin >> str[j]; q=0; str[i]=1; for(j=0;j<n;j++) if(str[j]==0) q++; if(q!=0) { conn[i]=new int[q]; done[i]=new int[q]; } quan[i]=0; for(j=0;j<n;j++) if(str[j]==0) { conn[i][quan[i]]=j; done[i][quan[i]]=0; quan[i]++; } } razrul(a); } void razrul(int a){ tstr[0]=a; int *tstr1; int ptstr=1,a0=a,i; while(1) { for(i=0;i<quan[a];i++) if(done[a][i]==0) { done[a][i]=1; a=conn[a][i]; tstr[ptstr]=a; ptstr++; break; } if(a==a0) break; } if(ptstr!=1) tstr1=new int[ptstr]; else return ; for(i=0;i<ptstr;i++) tstr1[i]=tstr[i]; for(i=0;i<ptstr-1;i++) { cout <<tstr1[i]+1<<" "<<tstr1[i+1]+1<<"\n"; razrul(tstr1[i+1]); } } |
|