|
|
вернуться в форумПоказать все сообщения Спрятать все сообщенияIs there any polynomial time solution? I can WAZZAP 14 ноя 2002 16:52 > Is there any polynomial time solution? yes. - if there is a cycle the answer is always "yes" - if there is a knot (ex. 2 2 edges), the answer is also "yes" - if graph is multigraph, yes too if all above is false just find the longest path in a tree and play with it's value in comparsion with route length > > Is there any polynomial time solution? > yes. > > - if there is a cycle the answer is always "yes" > - if there is a knot (ex. 2 2 edges), the answer is also "yes" > - if graph is multigraph, yes too "multigraph" : what is it? I got WA so many times,any trick? > > if all above is false just find the longest path in a tree and > play with it's value in comparsion with route length > > Thanks. I did not read the question well enough and thought that the race must start and end on vertices. How stupid of me! That is why I asked that stupid polynomial question. > > > Is there any polynomial time solution? > > yes. > > > > - if there is a cycle the answer is always "yes" > > - if there is a knot (ex. 2 2 edges), the answer is also "yes" > > - if graph is multigraph, yes too > "multigraph" : what is it? I got WA so many times,any trick? > > > > if all above is false just find the longest path in a tree and > > play with it's value in comparsion with route length > > > > Edited by author 23.07.2008 05:54 > "multigraph" : what is it? I got WA so many times,any trick? multigraph can have more than one edge connecting 2 vertices. Those edges can have different length. So, if there are two or more edges, connecting 2 vertices, this is just another cycle. This task is quite tricky and not well-right from the point of diskrete maths. For example, non-oriented graph can not have knots (by the difinition), but in this problem this is one of the "triks". but how to judge whether there's a cycle? do DFs and if there a return edge than u have a circle or do n Dijkstra's and if u can get back to the point than u have a circle I can't understand why if there is cycle, the answer is always yes -> what about this test: 3 3 1000 1 2 3 2 3 3 1 3 3 Edited by author 21.07.2009 12:43 Why YES? Petr Huggy (Pskov) 21 ноя 2010 12:32 Because there is a cycle with length 9, and we can ride this path unlimited number of times. "The race may start and finish anyplace on the road" |
|
|