|
|
back to boardHow can this be solved? Can anyone help?(+) Posted by asif 10 Nov 2002 22:15 Is there any polynomial time solution? I can Posted by WAZZAP 14 Nov 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
Re: I can Posted by Ural 18 Nov 2002 10:59 > > 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 a lot (+) Posted by asif 22 Nov 2002 13:43 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
> >
> > Multigraph Posted by WAZZAP 23 Nov 2002 17:03 > "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". Re: I can but how to judge whether there's a cycle? Re: I can 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 No subject
Edited by author 23.07.2008 05:54 Re: I can Posted by h1ci 21 Jul 2009 12:42 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? Because there is a cycle with length 9, and we can ride this path unlimited number of times. Re: I can Posted by yyll 8 Oct 2020 20:56 "The race may start and finish anyplace on the road" |
|
|
