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

Автор MacKenlly, история, 9 лет назад, По-русски

Не давно я наткнулся на эту задачу И уже довольно долгое время ломаю голову, почему и где программка зацикливается. Я надеюсь, вы — как опытные гуру, сможете мне помочь...


#include <fstream> #include <string.h> #include<string> #include <iostream> #include <cstring> #include <algorithm> #include <map> #include<cstdio> #include<vector> #include <string> using namespace std; int cat[1000]={0}; bool color[5000]={0}; int a[5000][5000]={0},n,k,c=0; int dfs(int i) { bool f=true; color[i]=1; if (cat[i]<=k) {for (int j=1;j<=n;j++) { if (color[j]==0&&a[i][j]==1) { f=false;if (cat[j]!=0) cat[j]+=cat[i];dfs(j);}} if (f) c++;} return 0; } int main() { cin>>n>>k; for (int i=1; i<=n; i++) cin>>cat[i]; for (int j=1; j<n;j++) {int x,y; cin>>x>>y; a[x][y]=1;a[y][x]=1;} dfs(1); cout<<c; return 0; }

Заранее спасибо)

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

N — до 105, а у тебя объявлена матрица смежности до 5000. При попытки перейти в вершину с индексом больше 5000, программа обращается в неизвестную область памяти, и происходит непонятно что.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    В тесте, который не проходит, размер входит в диапазон...

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +96 Проголосовать: не нравится

Позвольте для начала разнести некоторые вещи из вашего кода в пух и прах. Цель — рассказать, почему какие-то вещи делать не надо и как надо делать вместо этого.

  1. Начну с хорошего: спасибо, что выложили подсвеченную версию, а не просто скопировали код без оформления. На будущее: еще можно давать ссылку на посылки (кнопка с логотипом Codeforces в окне редактирования -> submission, номер посылки можно скопировать со страницы "попытки".
  2. Теперь то, что можно сделать лучше, основная претензия: отступы и форматирование кода. Когда вы хотите, чтобы ваш код кто-то прочитал, в том числе вы сами через десять минут (а вы просите помощи, то есть точно этого хотите), его следует оформлять в соответствии с некоторыми общепринятыми стандартами. Например, принято отделять все блоки кода (внутри фигурных скобок) отступами в несколько пробелов (некоторые используют вместо пробелов символ табуляции, но мешать точно не надо — у всех табуляцию имеет разную ширину). Подробнее можно посмотреть тут. Стилей расстановки отступов и скобок несколько, самые популярные — K&R и Олман, выберите один (какой больше нравится) и придерживайтесь его в коде. Почему так делать хорошо и нужно: стандартный вид кода делает чтение намного легче, например, я могу чисто визуально определить, внутри каких if'ов и циклов будет лежать каждая строчка и просто пропустить те, которые мне неинтересны. При отсутствии форматирования я вынужден читать каждый символ, что раздражает. Уважайте тех, кто хочет вам помочь: сделайте код легче для чтения. Если вы пишете в среде разработки (вроде Code::Blocks или Visual Studio), наверняка есть стандартная команда "отформатировать код". Если почему-то принципиально не хотите писать, как принято, можете пользоваться онлайн-форматтером перед вставкой кода, например, тут. Вот пример вашего кода после форматирования (вот этим форматтером, на который я сослался). Читать намного легче: все команды на разных строках, чётко видна структура dfs: что-то содержательное происходит только в случае cat[i] <= k, причём сначала идёт цикл по всем вершинам, удовлетворяющим какому-то условию, а потом как-то модифицируется некоторая переменная c. Таким образом человек, не знающий решения задачи и хода ваших мыслей, может его хотя бы попробовать восстановить.
  3. В C++ есть тип void, который можно указывать, когда функция ничего не возвращает. Например: void dfs(int i). Тогда возврат из середины функции пишется просто командой return;, а в конце функции можно вообще return; не ставить — он сам поставится. С функцией main так нельзя — она особенная и должна возвращать int. Опять же, ради повышения читаемости: если я вижу, что dfs возвращает некоторое значение, то я предполагаю, что оно где-то используется и очень удивляюсь, когда вижу return 0; и то, что результат вызовов dfs(1) и dfs(j) никак не используется.
  4. Глобальные переменные простых типов (int, double) и массивы из них в C++ по умолчанию инициализириются нулями (в отличие от локальных, в которых может быть любая фигня и поэтому надо инициализировать явно: int x = 0). Поэтому, в частности, вам необязательно их инициализировать нулями. Более того, конструкция int a[10] = { x } вовсе не заполняет массив иксами, как может показаться на первый взгляд — пример. Происходит что-то менее очевидное: все указанные в скобках элементы заполняются указанными значениями, а остальные — значениями по умолчанию. Запись int a[10] = { 0 } притворяется, будто бы она обозначает "заполни всё нулями", хотя это не так, поэтому так писать не стоит. Если у вас глобальный массив — оставьте его вообще без инициализации, он будет заполнен нулями. Если локальный (или хотите явно проинициализировать глобальный массив) — напишите int a[10] = {} — в этом случае все элементы точно заполнятся значениями по умолчанию.
  5. Если у вас какая-то константа, наделённая смыслом, встречается в коде хотя бы один раз (особенно если это константа из условия или ограничения на вход) — обязательно оформляйте это в отдельную константу, а не копируйте каждый раз. Почему: при копипасте есть риск ошибиться; вам наверняка потом захочется это константу исправить (в отладочных целях, например), и исправлять в одном месте намного проще, чем искать везде по коду (опять же, есть риск ошибиться при исправлении). Как надо: заводите константу с говорящим именем (например, MAX_N или MAX_VERTICES) и используете её. При этом не стоит использовать одну константу для разных по смыслу вещей: если у вас 1000 вершин и 1000 рёбер (и вы хотите хранить рёбра в списке), заведите разные константы: возможно, вы вспомните, что на самом деле вам надо хранить каждое ребро дважды (в одну сторону и в другую) или нужно добавлять дополнительные рёбра в граф. Например:
const int MAX_N = 5000;
int cat[MAX_N];
bool color[MAX_N];
int a[MAX_N][MAX_N];

Собственно, последняя рекомендация оказалась бы для вас спасительной: у вас размер массива cat не такой, как для остальных (14763809).

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    Большое спасибо за подробное объяснение!=) Выручил!

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    в конце функции можно вообще return; не ставить — он сам поставится. С функцией main так нельзя — она особенная и должна возвращать int

    на самом деле можно — по стандартам C99 и C++11 отсутствие return в main (и только в main) интерпретируется как return 0;

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      Во избежание недопонимания хочу уточнить: main всё равно обязана возвращать int, просто (в отличие от любой другой функции) у неё в конце как будто дописана строчка return 0;.

      И ещё, применительно именно к олимпиадному программированию: к моему великому сожалению, до сих пор во многих соревнованиях используется не C11 и даже не C99, а старый как мир C89, а в нём этого правила про подразумевающийся return 0 нет, а и его надо писать самостоятельно.

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

    Небольшие дополнения к тому, что сказал Егор:

    0) Если ты научишься оформлять свой код в "хороший" стиль — то спустя какое-то время ты начнешь писать с меньшим количеством багов, ты сам свой код будешь намного легче читать. Более того, как это ни странно, скорость написания кода со временем даже повысится, потому что ты, продумывая очередную строчку, будешь намного лучше ориентироваться в том, что написал выше. К тому же, стандартные алгоритмы будут запоминаться очень быстро, буквально после нескольких сданных задач.

    1) Почему ты все действия делаешь в одной строке? Опять-таки, в "хорошем" стиле одна точка с запятой — одна строка. Если действия делаются через запятую — то можно располагать их в одной строке. Не экономь строчки, ты осложняешь себе чтение кода. Лучше уж сделай разрешение на своем компьютере чуть поменьше или удали все лишние окна из своего компилятора.

    Так же между различными смысловыми частями кода(например, между различными функциями) лучше оставлять дополнительный перенос строки. Например:

    inline void bfs()
    {
        -здесь что-то написано-
    }
    
    inline int dfs()
    {
        -и здесь что-то написано-
    }
    
    int main()
    {
        -и даже здесь что-то написано-
    }
    

    2) В правилах "хорошего тона" есть еще один момент: битовые и логические операции стоит делать без пробела, остальные — с пробелом.

    Впрочем, мне говорят, что далеко не всегда и не везде так делают.

    int x = 5, y = 6;
    int binary = x&y;
    bool ternary = (x && y);
    cout << binary << ' ' << ternary << endl;
    

    3) Очень желательно, чтобы типы переменных соответствовали тому, как ты используешь. К примеру, насколько я вижу, свою матрицу a ты используешь как bool, а она при этом имеет тип int. Не надо так делать.

    4) Желательно ставить свои константы с некоторым запасом. Делается это так:

    const int MAX_N = 5000 + 13;
    

    где 5000 — это то число, которое указано в условии задачи, а 13 — это тот запас, который ты оставляешь.

    Иногда тебе в задачах требуется для некоторых массивов увеличить константу в несколько раз. Делать это можно двумя способами

    а)

    const int MAX_N = 5000 * 4 + 13;
    

    он очень плохой, но если у тебя размеры всех массивов 4 * 5000 — то почему бы и нет?

    б)

    const int MAX_N = 5000 + 13;
    
    int a[NMAX * 4], b[NMAX * 20], c[NMAX];
    

    этот способ более предпочтителен

    P.S. Разумеется, все вышеперечисленные правила не "железные" и ты, когда начнешь ими пользоваться, для себя выделишь некоторые исключения. Но в большинстве своем эти правила лучше соблюдать — тогда код будет получаться чистым и писаться будет буквально сам, очень быстро.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +61 Проголосовать: не нравится

      Удали свой пункт (2), пока никто не видел. В нем написана полная чушь.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      Соглашусь с пунктами 0, 1, 3.

      С пунктом 2 не соглашусь — он разный в разных code style. Я практически нигде не видел рекомендацию "не отделяйте бинарные операции пробелами", как раз везде пишут наоборот (в том же Google Code Style). Кстати, тернарные операции — это операции с трёмя аргументами (а такая ровно одна — cond ? res_true : res_false). Полагаю, имелись в виду битовые и логические.

      С пунктом 4 категорически не соглашусь — "делать константы с запасом" есть хак, подобный "а давайте добавим случайную +1 в формулу, авось пройдёт" — сдать задачу может помочь, но я считаю, что в процессе обучения и изучения алгоритмов, а также на работе так делать нельзя. Если автор не понимает, как работает программа, то что-то не так, а если понимает — то должен и понимать, нужен ли запас, и если да — какой точно. Например, если длина строки во входе равна 100, то нужен массив размером ровно 101 — плюс один символ на null terminator. Если я при этом читаю при помощи fgets, то нужен массив размером 103 — один символ на null terminator и два символа на перевод строки в Windows. Особенно эти ошибки  ± 1 любят возникать в каких-то динамиках и тому подобному. В процессе обучения, мне кажется, очень важно думать и полностью понимать происходящее.

      Рекомендацию "а" из пункта 4 я считаю вредной — вводится константа с неверным именем — MAX_N не равен 5·4000, так что константа не только не помогает, но и вредит при чтении кода — начинает казаться, что на самом деле n ≤ 10 000 и возникает закономерный вопрос: а где, собственно, требуемый решению четырёхкратный запас? Разумным считаю вариант "б", где размеры массивов вычисляются из констант на месте. Если какая-то константа часто возникает (например, 3 * MAX_N), возможно, стоит её вынести под каким-то названием вроде "размер массива с запасом для динамики" или "размер для массива с зацикленной строчкой" (скажем, CYCLED_STR_ARR_SIZE = 3 * MAX_N + 1).

      На контестах некоторые, к сожалению, любят делать запас в сотню-другую элемнентов и аргументируют это "по-другому не заходит" вместо того, чтобы понять, почему именно нужен запас в данном конкретном случае. Иногда такие запасы маскируют выход за границы массивов, а в сочетании со статическими массивами фиксированного такие ошибки становится невозможно отловить на маленьких тестах — просто потому что массива хватает. Поэтому я везде, где могу, выделяю вектора размера в точности такого размера, как мне надо, без запасов. Если я ошибся на десять — это примерно с одинаковой вероятностью будет бред и на большом тесте, и на маленьком.

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Я немного подправил то, что выше. Конечно, имелись ввиду битовые операции и логические, с утра такая каша в голове иногда бывает :) . Спасибо за замечания. Однако...

        По поводу пункта 2 — я где-то в свое время услышал/увидел такой стиль кода, где именно — сейчас уже не помню. Сам я в то время не обращал внимания на стиль написания кода(как и автор нынешнего топика), однако перестроил свой код именно под стиль "между некоторыми операциями лучше ставить пробел, между некоторыми — нет". И выступая в составах различных команд СГУ, наблюдая за различными кодерами в моей команде, я пришел к выводу, что все это правило используют. Операции, которые разделяются пробелом/не разделяются, различались у всех, однако у всех класс "беспробельных" случаев не был пустым.

        Пункт 4. Позволь мне, в свою очередь, не согласиться с тобой :) . Моя идея — давайте будем использовать один и тот же аппарат что для оценки времени, что для оценки памяти. А именно — давайте что для первого, что для второго случая будем считать асимптотику и константу у этой асимптотики. Так мы гораздо быстрее изучим аппарат асимптотических оценок. И не только сам аппарат, но и "частные случаи", когда нужно чуть внимательнее считать оценку.
        Разумеется, оценка памяти нужна гораздо более тщательная. Однако, раз она нужна более тщательная — значит, мы еще быстрее сможем изучить аппарат :) .