|
|
перепроверте тесты задачи B pls Перепроверили :) а теперь условия pls исходя из условий задачи необходимо вывести номера хобитов(строк) состоящих из одних нулей предворив список на отдельной строке числом таких строк засада при случае когда таких строк нет( возможен когда матрица содержит ошибочные данные тк как всегда должен имется легчайший хобит) ВОПРОС почему так мало ac? у такой на первый взгляд простой задачи? намекните pls! not so easy, try this test: 3 0 0 0 1 0 0 1 0 0 answer: 2 2 3 or this: 3 0 0 0 0 0 0 1 1 0 answer: 2 1 2 По-моему так это NP-полная задача на 100 узлов Edited by author 16.09.2010 19:25 Эта задача решается за O(n^2) + Кун. Так что совсем быстро :) 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! 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 This problem can be solved in O(N^3) time. 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). I got AC with very optimized backtraking, I think the problem has simple solution.. Could you tell me your algo or send me your code in case if you solved it without backtraking ? e-mail: www-www-www@mail.ru efrcom [at] inbox [dot] ru Edited by author 04.05.2007 01:03 closed! AC! Edited by author 27.03.2007 14:51 |
|
|