|
|
вернуться в форумinteresting otimization Послано svr 22 окт 2007 08:46 Firstly I had hypothesis that snake in optimal solution has one circle and comes back having maximum two possible visitings of some positions by it's head. And It is right. Ac at last. This problem is on searching simple circles in graph. But not in all grid but on BFS created points only. After I added program for bicomponents and began to skip edges during dfs searching which have no another edges in the same component. This shorten time from 0.9c to 0.3 c. After that I added demand that first edge in first call of dfs must be procecced only once.It allowed me to get Ac 0.093 An to take 1 place in problem raiting. Edited by author 07.01.2009 12:59 |
|
|