Блог пользователя ikuznecov

Автор ikuznecov, 13 лет назад, По-русски

Подскажите пожалуйста, как решать эту задачу???


Дан граф до 200 вершин. Нужно сказать, какое минимальное количество вершин необходимо удалить, чтобы все оставшиеся вершины стали изолированными (не имели соседей).


Спасибо огромное!!

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Я очень удивился, увидев, кто автор этого комментария :)
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Ты СОВЕРШЕННО не понимаешь в чем суть anonymous-a. Anonymous это не «о, привет чуваки, зацените прикольную сцылку я нашел, гыгы». Anonymous это не псевдоинтеллектуальные обсуждения. Anonymous это участник, который выражает личное мнение, пытаясь при этом выразить общее, пусть даже и скрытое, мнение сообщества. 

      Anonymous бездушно подпишется под чем угодно, предпочтения anonymous-а не основаны на здравом смысле, бесцельные споры — его стихия, он — истинное лицо интернета.

    • 13 лет назад, # ^ |
        Проголосовать: нравится -13 Проголосовать: не нравится
      Вообще велосипедопостерам надо бы как-то мягко намекнуть что хумор повторённый более 256 раз теряет остроту, даже если с вариациями. Правда такие ребята намёки понимают с 65536 раза...
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Во многом их можно понять - наблюдать в прямом эфире вопросы лентяев, которым проще зарегаться на codeforces и написать пост, чем погуглить, - немного надоедает. И лучше уж велосипеды с вариациями, чем обычные ссылки.

        А по поводу добавления к множеству велосипедистов Alex_KPR - я почему-то не удивлён :)
        • 13 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится -16 Проголосовать: не нравится

          В этом-то я их понимаю, т.к. на codeforces лентяев ещё сравнительно мало по сравнению с профессиональными форумами. Но учитывая что лентяй велосипедной шутки не поймёт а все остальные её уже стопиццот раз видели - только лишний раз в прямом эфире тему поднимать. ;-)

          Ы-ы-ы! :D
          Раньше у моих сообщений автоматически проставляли 1-3 минуса какие-то таинственные поклонники. А сегодня я явно оставил далеко позади эти достижения. Чувствую себя польщённым - гы-ы-ы! Давайте до -100 дожмём!
        • 13 лет назад, # ^ |
            Проголосовать: нравится -10 Проголосовать: не нравится
          Собсно надо просто дожать у администрации идею запрета постов для аккаунтов вне рейтинга - и троллей и спамеров и лентяев сразу чудесным образом стало бы меньше. А так только ходят и удивляются - откуда же это берутся все эти дуралеи на сайте со свободной регистрацией?
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            А чем тебе AWPRIS неугодил ? O_o

            Так хорошо поднялся на последней стихо-шутке в его последнем посте. Зачем он его спрятал?

            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Олег, добрый день!

              Думаю что глубоко уважаемый мною Анатолий Васильевич без проблем получит у администрации форума личный, почётный и пожизненный исключительный допуск.

              Администраторы уж наверное не глупее нас и их квалификация позволит им этот вопрос технически решить. ;-)
        • 13 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится
          Ты не совсем прав. 

          С одной стороны, масса подобных вопросов в общем блоге немного раздражает.

          Но с другой стороны, я еще помню время, когда толком не знал английского языка, не знал алгоритмов и не умел гуглить. Часто в такой ситуации не остается ничего, кроме как попытаться задать свой глупый вопрос на каком-нибудь ресурсе наподобие этого.

          Конечно, идеальным решением было бы ввести модератора(ов), который мог бы фильтровать вопросы новичков в отдельное место.
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Ну если не умеешь гуглить - первое, что надо сделать, - научиться, т.к. это очень важное умение.

            В крайнем случае, если прогуглил 3 часа подряд и ничего не нашёл, - можно начать спрашивать у друзей/знакомых. И только если даже это не помогло - спрашивать у всего сообщества.

            Тут, как мне кажется, имеет место неуважение к чужому времени. Вместо того, чтобы потратить 10 минут своего времени, человек тратит 1000 минут чужого, создавая этот пост в публичном блоге.
      • 13 лет назад, # ^ |
          Проголосовать: нравится -9 Проголосовать: не нравится
        просьба, повторённая 4294967296 раз, должна окончательно выбесить до того, как она повторится в 18446744073709551616-ый раз...
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Александр, помни - Орёл не ловит мух. Тебе не проще было забить меганский болт на этот пост нежели шариться по инету в поисках нот?
          • 13 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

            Доформулирую Вашу идею.

            Не проще ли забить меганский болт на строительство Охта-центра, нежели приходить на демострации и выступать против?

            • 13 лет назад, # ^ |
              Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

              Не начинайте снова-здорова про митинги-петинги. В 21 веке по-моему только тупой ещё не догадался что демонстрации это один из наиболее сложных и малоэффективных способов борьбы с властью. Точно так же как кросспосты в блогах мало спасают от лесных пожаров. Почему-то население продолжает упорно путать эти два случая. ;-)
              • 13 лет назад, # ^ |
                  Проголосовать: нравится +1 Проголосовать: не нравится
                Вам сколько лет?
                • 13 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  Аноним пытается выяснить личную информацию об участниках? Я плакал. Неужели для получения на этот вопрос слабо инетом воспользоваться?

                  Взываю к Вашим интеллектуальным способностям и умению пользоваться сетью Вконтакте!
                  • 13 лет назад, # ^ |
                    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

                    Хоть бы цитаты из Стругацких точно писали. Я намекнул Вам, что Вы мне по непонятной причине тыкаете (я вижу, это Вы уже поняли).
                    • 13 лет назад, # ^ |
                        Проголосовать: нравится 0 Проголосовать: не нравится
                      1) Не обижайтесь, я просто не всегда сразу вспоминаю с кем мы на вы а с кем на ты.

                      2) С другой стороны возраст и соц.статус Анонимуса неизвестны, а априорно он не связывается с образом заслуживающим почтительного обращения. Это, сорри, карма анонимусов такая. ;-)

                      P.S. Цитаты АБС не было. Перечитал сообщения - не нашёл что имеется в виду. Я в литературе не оч силён.
                      • 13 лет назад, # ^ |
                          Проголосовать: нравится 0 Проголосовать: не нравится

                        Счастье! Для всех! И пусть никто не уйдет обиженным!!!
                        В источнике:
                        СЧАСТЬЕ ДЛЯ ВСЕХ, ДАРОМ, И ПУСТЬ НИКТО НЕ УЙДЕТ ОБИЖЕННЫЙ!

                        • 13 лет назад, # ^ |
                            Проголосовать: нравится 0 Проголосовать: не нравится
                          Ах вот оно что... Страницу вы значица отыскали и теперь оно, значица, сыто и довольно?

                          Фраза суть передаёт верно и надеюсь товарищи авторы на меня не обидятся. ;-)

                          широкастранамояроднаямноговнейвсегохорошего
                          • 13 лет назад, # ^ |
                            Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

                            Разница принципиально меняет смысл.
                            Страницу я отыскал еще до вопроса, разумеется.

                            P.S. сейчас придет г-н Хаустов и скажет свой веский аргумент про социальный статус.
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Тем более одно дело когда пытаются организовывать демонстрации против решений политических деятелей, которые годами бессменно сидят в своих креслах - и совсем другое - пытаться велосипедами что-то объяснить человеку, который может даже не вспомнит на каком форуме он регился чтобы задать вопрос. :D
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Есть те, кто будет такое стучать по нотам ?
    :) 
    • 13 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      Верхняя строчка напоминает "сбор" из приложения к Строевому Уставу Вооружённых Сил :D
  • 13 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    Вполне нормальный вопрос для этого ресурса, что не могу сказать про ответ. Зато "сообщество" считает наоборот... :о
    • 13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

      Совершенно ненормальный вопрос для ЭТОГО ресурса, знаете ли...
      По крайней мере, интересного обсуждения (получилась только простыня велосипедов) и пользы для "сообщества" вопрос, который самостоятельно гуглится за пару минут, не несет.
      • 13 лет назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится
        Не могу не согласиться с тов. Романом. Вопрос по крайней мере соответствует тематике ресурса и под запрещённые администрацией категории не подпадает. Тут и участники с "солидными" цветами ников порой задают вопрос "найдите ошибку в моём коде, а то я сам не могу". Я считаю что это на порядок глупее.

        Если на вопрос не хочется отвечать, то не надо этого делать. Тем более не надо лепить велосипеды, раз уж Анонимус жаловался что тов. Мирзаянов его лично попросил такой ерундой не заниматься.
  • 13 лет назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится
    Спасибо, я как раз думал что послушать.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Если я правильно понял то вот.
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    Не знаю, что вы имели ввиду, но автор спрашивает про NP-полную задачу поиска максимальной антиклики. Поправьте меня, если я не прав.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Скорее всего вы правы.
      Автор спрашивал "какое минимальное количество вершин необходимо удалить" , мне показалось что это задача о минимальном контролирующем множестве вершин.
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Почему у RodionGork на всех коментах -512? ))
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    наверное потому, что как минимум 512 различных пользователей кликнули у его комментариев на "мне не нравится" ;)

    К. О.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    потому что кто-то исходники страницы подрпавил)
    вклад у него остался тот же)

    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Админам нужно срочно искать shell'ы или что нибудь подобное.
      К.О.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Не, вклад кажись на единичку уменьшился - я с любопытством слежу за этим делом т.к. формула расчёта вклада это сакральная тайна и её свойства хочется угадать. ;-)

      Другое дело - я думал, что -512 это некий предел после которого система "поломалась" или упёрлась в дно. Однако теперь я опять чего-то не понимаю. А жаль, такая кругленькая циферка была, так красиво!

      Главное что хотелось уяснить - мне давно мерещится что есть один или несколько человек которых проблема массового управления плюсиками-минусиками видимо интересовала и они её видимо решили. Думаю, я не ошибался... ;-)
  • 13 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    Жандоса заинтересовал способ быстрого набивания рейтинга комментариев? :)
13 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
Такой вопрос:

Есть ситуация. Я не могу решить задачу, нет человека, который мог бы объяснить, не смог нагуглить.
Лучше ли мне:
а) Пойти спросить на форуме КодФорсес
б) Спросить кого-нибудь в личной переписке(не знакомого лично человека)

Уже несколько раз я пользовался вторым вариантом и мне всегда помогали, за что им(RasifielOStfreopendaftcodercmd) большое спасибо.
Так как же поступать новичкам? Лучше ли, если каждый создаст по блогу и Вы отшутитесь, но поможете, или лучше все вас закидают сообщениями в личку?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    такая тема уже всплывала, и, если мне не изменяет память, Паша Хаустов прекрасно описал действия пользователя, который хочет получить информацию о решении какой-либо задачи

    на самом деле всё очень просто: если ты non-rated, который создан 15 минут назад и просишь "памоч с задачОй", то, мягко выражаясь, тебя отправляют покататься на велосипеде

    если ты цветной участник, то грамотно сформулировать вопрос по решению нетривиальной задачи, которую нельзя нагуглить в два клика, более чем достаточно
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Я такое заметил:

    Можно задать вопрос на который сколько-то человек знают ответ - тогда велика вероятность, что нарисуют велосипед. (притом не факт что велосипедер действительно знал ответ или правильно прочёл задание)

    Можно задать вопрос, на который ответ неизвестен или над которым реально нужно думать - тогда сделают вид что не заметили и после одного-двух неполезных комментов пост исчезает из прямого эфира.

    В общем, воинствующий ламеризм. ;-)

    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      а мне кажется, что не очень правильно смешивать с говном окружающих тебя людей ;)

      в качестве эксперимента попробуй покричать на Красной Площади "все русские - ублюдки" ;)
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Александр, привет! ;-)

        Ты ответь прямо. Вон Ignat утверждает что задача NP-полная. Поскольку он красный - я готов ему поверить. Однако если автор получил её как учебную а там 200 вершин - то это как-то странно.

        Твоё какое мнение?

        Кстати, вместо велосипедов могу тебе порекомендовать классное супероружие.
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          привет :)

          я думаю, что автор даже не смог задачу сформулировать корректно, чтобы донести её пользователям ресурса

          вообще да, она NP-полная, причём адски классическая

          P. S. велосипеды мне нравятся больше :)
13 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится
вау, пост появился примерно тогда же, когда воронеж опубликовал задачи отборочного тура, одна из которых сводится к максимальному вершинному покрытию в графе на 100 вершин