| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
| How can this be solved? Can anyone help?(+) | asif | 1227. Чемпионат по ралли | 8 окт 2020 20:56 | 11 |
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" |
| WA 3 | So Sui Ming | 1227. Чемпионат по ралли | 18 дек 2019 12:00 | 3 |
WA 3 So Sui Ming 6 сен 2017 11:01 I passed all test cases mentioned in the discussion.
There are 4 tests in my algorithm:
- is there a loop (from M and N) ?
- is the graph connected ?
- is there a cycle?
- for each component of the graph:
find the longest path and compare the length with S
any hint?
Edited by author 06.09.2017 11:02
Edited by author 06.09.2017 11:02 i had problems with 3rd test case. this input should help you:
1 1 5
1 1 2
the key here was to look closely at restrictions:
1 ≤ M ≤ 100; 1 ≤ N ≤ 10 000
assuming there could not be several ways from different x and y, and no loops from x to x, there should be at most 4950 connections between cities 3rd test contains road from X to X, so answer is "YES" |
| In case you have WA7 | Ilistratov | 1227. Чемпионат по ралли | 28 окт 2019 20:09 | 1 |
Graph can have loops and multiple edges.
Edited by author 28.10.2019 20:10 |
| WA#17 Help, please | Ann | 1227. Чемпионат по ралли | 19 мар 2019 00:15 | 1 |
An example from other discussions:
input:
4 3 12
1 2 5
1 3 4
3 4 4
output:
YES
displays the correct answer.
Tell me more examples, please.
In the algorithm, I check loops, two-way roads, cycles, and then look for a way longer than necessary.
UPD: WA#18
Edited by author 20.03.2019 19:17 |
| WA#18 | Bogolyubkiy | 1227. Чемпионат по ралли | 17 сен 2017 19:32 | 2 |
WA#18 Bogolyubkiy 4 май 2010 19:20 Can you suggest an example for this test? 4 3 40
1 2 10
2 3 20
2 4 20
Right answer: YES |
| Some Hint : | Adhambek | 1227. Чемпионат по ралли | 10 ноя 2014 13:58 | 1 |
you can use to check "YES" that simple DSU algorithm.
because DSU algorithm gives us all cycle, knot, multigraph ... so on
|
| If you have WA 11 or WA 17 | Mamuka Sakhelashvili [Freeuni] | 1227. Чемпионат по ралли | 16 фев 2014 22:46 | 1 |
try this test
input:
4 3 12
1 2 5
1 3 4
3 4 4
output:
YES |
| WA 12 | Hristian Hristov | 1227. Чемпионат по ралли | 4 окт 2011 02:23 | 1 |
WA 12 Hristian Hristov 4 окт 2011 02:23 Can you give me some tests. I check if it is multigraph and if there are cycles. After that I get the longest path and if it is lower than S I ouput NO. But still WA :( |
| Why WA#9? | Lucifer | 1227. Чемпионат по ралли | 1 дек 2010 19:49 | 2 |
try this:
input:
3 2 12
1 2 10
2 3 5
output:
YES
if you WA#17 try this:
input:
4 3 12
1 2 5
1 3 4
3 4 4
output:
YES
GOOD LUCK!!! |
| Pls answer me! | Rostislav | 1227. Чемпионат по ралли | 5 ноя 2008 19:47 | 5 |
What is the output?
1 1 3
1 1 2 |
| To admins | Loky_Yuri [USTU] | 1227. Чемпионат по ралли | 13 июл 2007 01:45 | 2 |
Rather simple tests…
For this test my AC program gives “NO”:
4 2 13
1 2 15
3 4 10
But the correct answer is YES.
So as I understood, in all your tests, if graph is unconnected and there is no cycle in it, then the max length of path always contain the last (m) vertex…
So all programs which use this algorithm passed all your tests:
First, check knots, multigraph;
Second, for (I, 1, n) - check is the i vertex is in the circle;
Third, find the max length of path of that tree, which contain the last vertex; and compare it with s.
INSTEAD: Third, find the max length of paths ALL TREES, and all of them compare with s.
Sorry for my English. |
| Be careful that the graph isn't necessarily connected! | Maigo Akisame (maigoakisame@yahoo.com.cn) | 1227. Чемпионат по ралли | 22 окт 2004 05:03 | 1 |
|
