Обсуждение @ 1569. Сети в Исети @ Timus Online Judge

araifr What is the proper solution? (Got AC with a hack, my solution inside) [2] // Задача 1569. Сети в Исети 7 ноя 2018 13:19

Felix_Mate What is test 17? [2] // Задача 1569. Сети в Исети 14 янв 2016 22:44

RoBa Is the edge direct or undirect? [1] // Задача 1569. Сети в Исети 6 окт 2007 14:23

Razdolbay from SIS Tests (to admins) [1] // Задача 1569. Сети в Исети 4 дек 2007 02:47

Samsonov Ivan (Rybinsk SAAT) wa #4 [11] // Задача 1569. Сети в Исети 7 окт 2007 19:00

Please give some test

Todor Tsonkov Re: wa #4 [10] // Задача 1569. Сети в Исети 7 окт 2007 22:00

Why BFS doesn't work ? Can you give some tests ?

Victor Barinov (TNU) this test helped me to get AC // Задача 1569. Сети в Исети 7 окт 2007 22:27

6 9
5 6
3 4
2 4
1 5
3 6
1 2
1 6
4 5
3 3

shilp Re: wa #4 [8] // Задача 1569. Сети в Исети 7 окт 2007 22:42

i make a shortest path tree (i know i do it correctly) from the every vertex of the graph, but even that is giving me a WA on #17... can someone please give me a test case where that would fail?

@Todor
BFS won't work in a case like
6 6
1 2
2 5
1 3
3 5
3 6
3 4

if you make a BFS tree by searching the lower indexed vertices, starting from 1, then 5 would be committed under 2 where as it should be committed under 3,
even if you are constructing a tree from 3 in the above case i am sure a case can be formed that the above anomaly is exploited.

Loky_Yuri [USTU Frogs] Re: wa #4 [7] // Задача 1569. Сети в Исети 7 окт 2007 22:55

I have WA #17 too. But I don't understand why in your test BFS doesn't work?
6 6
1 2
2 5
1 3
3 5
3 6
3 4
My prog gives this answer:
1 2
1 3
3 4
3 5
3 6
It's correct, isn't it?

shilp Re: wa #4 [6] // Задача 1569. Сети в Исети 7 окт 2007 23:31

its correct.. yes..
i am saying that a BFS would construct the shortest paths for sure, but it would do so in a greedy format that will most probably give a graph with a sub-optimal diameter, so perhaps will a shortest path tree.. i even tried constructing the BFS with highest degree first but none of it seems to work..

any idea?

diver_ru (Fishburg SAAT) WA 17? Look here(+) [5] // Задача 1569. Сети в Исети 9 окт 2007 16:32

Look at the test, given by Victor (thanks him):
6 9
5 6
3 4
2 4
1 5
3 6
1 2
1 6
4 5

Answer will be
1 5
2 4
3 4
5 4
6 5
and maximum distance equal 3 (in edges), not 4!

svr Re: WA 17? Look here(+) [3] // Задача 1569. Сети в Исети 16 окт 2007 00:04

How are you may start BFS programming
without mathematical characterization of
optimal solution. I found with difficulties
in internet that it is tree of shortest pathes
from absolute centre of graph.
Thus you need in two programs
1) Finding absolute centre(Hacimi)
2) Dejkstra for shortest paths.

P.S. Glad to confirm with help of 1569 My Hakimi algorithm realization.
But, of course, we don't need Hakimi algo to solve this problem. When edges have equal wheightes absolute centre
or in vertex or in middle of the edge.

Edited by author 02.06.2008 16:18

Denis Koshman Re: WA 17? Look here(+) // Задача 1569. Сети в Исети 14 авг 2008 13:52

I have found algo here:
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.5609

Thanks Victor for his test, I've found a bug (as usual, I used some outer loop variable inside inner loop. ARGHHHHH!)

Edited by author 14.08.2008 14:01

Edited by author 14.08.2008 14:01

Tolstobrov Anatoliy[Ivanovo SPU] Re: WA 17? Look here(+) [1] // Задача 1569. Сети в Исети 25 сен 2008 20:12

What is the complexity of Hakimi algo?

svr Re: WA 17? Look here(+) // Задача 1569. Сети в Исети 25 сен 2008 21:28

I repeat! You don't need Hakimi algo!
Apply your shortests path algo also to the middles of the edges as sink of searching.

Azad Re: WA 17? Look here(+) // Задача 1569. Сети в Исети 13 июл 2010 02:11

My program gave the following output:

1 5
3 6
1 2
1 6
4 5

Is that correct?

Denis Koshman Please add full graph 100x100 // Задача 1569. Сети в Исети 14 авг 2008 14:09

LX&R Bacherikov [KNU] TO ADMINS // Задача 1569. Сети в Исети 29 ноя 2007 18:25

Обсуждение задачи 1569. Сети в Исети