Обсуждение @ 1533. Толстые хоббиты @ Timus Online Judge

Victor Barinov (TNU) How to solve correctly? [3] // Задача 1533. Толстые хоббиты 31 окт 2007 18:20

Hi!

I know that exists theorem:
Minimal number of paths that cover such graph equals to maximal number of independent vertices.

If I found this paths how can i recieve necessary vertices?

Thanks!

svr Re: How to solve correctly? [2] // Задача 1533. Толстые хоббиты 31 окт 2007 20:21

I think that it is some clever ways to solve NP problems.
It works only in authors limits.
O(n^3)exists!
Apply bipartie maximal cardinality matching.
Standard matchig programm must be
strengthening by finding minimal vertex covering.
All vertex out of minimal covering - hobbits!

Edited by author 02.11.2007 09:02

Sandro (USU) Re: How to solve correctly? [1] // Задача 1533. Толстые хоббиты 31 окт 2007 23:21

This problem can be solved in O(N^3) time.

Denis Koshman Re: How to solve correctly? // Задача 1533. Толстые хоббиты 24 авг 2008 17:34

Victor. To solve what you want, you should find maximum clique in inversed transitive closure graph. Anyway, such level of abstraction leads to NP solution, try some other way. Transitive closure graph has some extra properties which allow O(N^3).

Обсуждение задачи 1533. Толстые хоббиты