How 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"