Разобрался в сабже, хочу найти задачек по теме. Беглый поиск дал немного результатов. Накидайте, пожалуйста, ссылок)

Что уже нашел я:

http://acm.timus.ru/problem.aspx?space=1&num=1553

Что есть в комментариях:

http://www.usaco.org/index.php?page=viewproblem2&cpid=102
http://www.codechef.com/problems/QTREE
http://codeforces.me/contest/226/problem/E

P.S. Буду обновлять список ссылок по мере поступления

Дан ориентированный граф. Количество вершин порядка десяти в четвертой, количество ребер порядка десяти в пятой. Нужно найти минимальное количество ребер так, чтобы граф стал сильно связным. Как это сделать? Я понимаю, что нужно разделить граф на компоненты сильной связности, потом подсчитать у стольких компонент нет исходящих ребер и у скольких нет входящих. Ответом будет максимум из этих чисел. Проблема в том, что я не могу понять, как потом эти ребра построить.

Введение

Идея поста появилась после обсуждения дженериков в java с Slamur. Он продемонстрировал на примере задачи 20C - Алгоритм Дейкстры? скорость работы кода с дженериками и без. Большая ли получилась разница, судите сами. Вот код с дженериками и без. Внятных объяснений разницы я загуглить не смог, поэтому тех, кто знает в чем дело, прошу разьяснить ситуацию. После этого я заинтересовался: а как обстоят дела с шаблонами C++? Да и не только с ними, но и вокруг них. Итак...

Поехали

Шаблоны C++ есть только в коде. В исполняемом файле их уже нет. Для каждого нужного типа создается свой класс/структура или функция. Тестировать различные способы я решил все на той же задаче про алгоритм Дейкстры(сначала). После измерил у себя искуственную задачу, но об этом позже. Изначальное желание просто протестировать реализацию с шаблонами и без вылилось в более широкий набор интересностей.

• Реализация полностью на стандартных структурах данных
• Своя шаблонная пара
• Своя не шаблонная пара
• Своя не шаблонная пара + свой не шаблонный контейнер
• И наконец своя куча + свои пары, все не шаблонное

Стандартные структуры данных

Тут в общем-то рассказывать нечего. Просто протокол тестирования. Отмечу только время работы: 140 мс.

Свои шаблонные пары

Не раз видел комментарии, что std::pair — это тормозящая лажа. Я хоть и относился к ним с недоверием, но наивно полагал, что это не голословные утверждения. Точнее, полагал до тех пор, пока не заглянул в их исходный код. А вот и он. Да, выглядит страшно и непонятно, но если поразбираться, то становится совсем непонятно, почему же это они "тормозят". Однако я все равно решил написать свои шаблонные пары, и протестить их.

template<typename T, typename U>
struct Pair {
  T first;
  U second;
  
  Pair()
  { }
  
  Pair(T f, U s) :
    first(f),
    second(s)
  { }
  
  bool operator < (Pair<T, U> o) {
    return first < o.first 
        || (first == o.first && second < o.second);
  }
  
  bool operator > (Pair<T, U> o) {
    return first > o.first 
        || (first == o.first && second > o.second);
  }
  
  bool operator == (Pair<T, U> o) {
    return first == o.first && second == o.second;
  }
};

template<typename T, typename U>
Pair<T, U> make_Pair(T f, U s) {
  return Pair<T, U>(f, s);
}

Вот так они реализованы у меня. А теперь смотрим на протокол тестирования. Хм, те же 140 мс. Все получилось так же, как и со стандартными. Я не утверждаю, что стандартные плюсовые пары — идеал оптимизации, но они как минимум ничем не хуже своих "обычных" пар.

Уходим от шаблонов

Теперь давайте посмотрим, как поведут себя пары без шаблонов. Код прямо здесь приводить не буду, будет ссылка на посылку. Итог получился не сильно быстрее: 125 мс. Разница небольшая. Критично это или нет, наверное, стоит смотреть в индивидуальном порядке.

Финт ушами

Давайте вспомним, как объявляется очередь с приоритетами.
prioriry_queue< тип, контейнер, компаратор > С типом мы уже разобрались, это наши любимые не шаблонные пары. Компаратор тоже понятен. Давайте напишем свой контейнер на массиве, чтобы не происходили постоянные реаллокации. Для меня это было интересным опытом :) Сначала я написал то, что думаю, потом пытался скомпилить и исправлял вылезающие ошибки. И все-таки это удалось (:

struct cont {
  typedef Pair value_type;
  typedef Pair& reference;
  typedef const Pair& const_reference;
  typedef int size_type;
  
  int sz;
  Pair a[LIM];
  
  cont() :
    sz(0)
  { }
  
  value_type* begin() {
    return a;
  }
  
  value_type* end() {
    return a + sz;
  }
  
  void push_back(Pair x) {
    *(a + sz) = x;
    sz++;
  }
  
  void pop_back() {
    sz--;
  }
  
  const value_type front() {
    return *a;
  }
  
  size_type size() const  {
    return sz;
  }
  
  const_reference front() const  {
    return *a;
  }
  
  bool empty() const {
    return sz == 0;
  }
};

Результат получился интересный. 109 мс, но разница все равно небольшая...

Все мое!

Просто ссылка, результат не впечатлил. 156 мс. Не сильно, но дольше.

Поехали, дубль 2

Хорошая, конечно, задача, но там есть и еще всякие факторы, влияющие на время, да и данных не так много, да и тесты не идеальные. И вот, что сделал: создал файл, на достаточно большое количество данных и протестировал все на нем. Создавал так:

fout = open("in", "w")

arr = [100, 1000, 10000]

for m in arr:
    for i in xrange(1, m + 1):
        for j in xrange(1, m + 1):
            fout.write(str(i) + " " + str(j) + '\n')

Компилировал плюсовые коды так:

g++ -O2 -Wall -o "a" "a.cpp"

И вот, что получилось:

1) Только STL

2) Мои шаблонные пары

3) Мои не шаблонные пары

4) Мой контейнер

5) Моя очередь с приоритетами

Выводы

Ну что тут сказать... Мой код не претендует на премию за чудеса оптимизации, но он и не самый худший из того, что можно было бы написать. На мой взгляд разница совсем не существенная, что показало "тяжелое" тестирование. Особенно если принять во внимание, что на результаты влиял не только код, но и общее поведение системы(да и хром работал). Пожалуй, сказать можно только то, что моя реализация кучи проигрывает стандартной :) А остальное практически идентично отработало. Итого: STL — добро! Критика приветствуется. Все еще помните вопрос про дженерики в java? Очень хочется узнать ответ.

Введение

Превратим обход в ширину в алгоритм Дейкстры за (n * log(n) + m * log(n))!
Данная статься предназначена в основном для участников div2, но я так же надеюсь, что и некоторым немного более продвинутым программистам будет интересно почитать. В этой статье я хотел бы описать основные алгоритмы для решения задач на графы. Однако, материала, пожалуй, не хватит, чтобы решать сложные задачи, но многие идеи, описанные здесь, вполне можно будет попробовать использовать и на сложных задачах. Материал из этой статьи можно представить, как фундамент, для изучения продвинутых алгоритмов на графах. Итак, начнем.

Обход графа в ширину

Первый алгоритм, который хотелось бы описать, и который однозначно нельзя пропустить — это обход графа в ширину. Что же это такое? Давайте немного отойдем от формального описания графов, и представим себе такую картину. Выложим на земле веревки, пропитанные чем-нибудь горючим, одинаковой длины так, чтобы ни одна из них не пересекалась, но некоторые из них касались концами друг с другом. А теперь подожжем одно из пересечений. Как будет вести себя огонь? Он равномерно будет перекидываться по веревкам на соседние пересечения, пока не загорится все. Нетрудно обобщить эту картину и на трехмерное пространство. Именно так в жизни будет выглядеть обход графа в ширину. Теперь опишем более формально. Пусть мы начали обход в ширину из какой-то вершины V. В следующий момент времени мы будем просматривать соседей вершины V(соседом вершины V назовем вершины, имеющий общее ребро с V). Для наглядного представления, приведу картинку.

Здесь мы начали обходить граф в ширину из вершины C. Затем мы перешли к рассмотрению вершин A, B и E.

Реализация обхода в ширину

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

void bfs(int u) {
  used[u] = true;
  queue<int> q;
  q.push(u);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = 0; i < (int) g[u].size(); i++) {
      int v = g[u][i];
      if (!used[v]) {
        used[v] = true;
        q.push(v);
      }
    }
  }
}

В этой реализации g — это список смежных вершин, т.е. в g[u] лежит список смежных вершин с u(в качестве списка использован std::vector), used — это массив, который позволяет понять, в каких вершинах мы уже побывали. Здесь обход в ширину не делает ничего, кроме самого обхода в ширину. Казалось бы, зачем? Однако его можно легко модифицировать для того, чтобы искать то, что нам нужно. Например расстояние и путь от какой-либо вершины до всех остальных. Следует заметить, что ребра не имеют веса, т.е. граф не взвешенный. Приведем реализацию поиска расстояний и путей.

void bfs(int u) {
  used[u] = true;
  p[u] = u;
  dist[u] = 0;
  queue<int> q;
  q.push(u);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = 0; i < (int) g[u].size(); i++) {
      int v = g[u][i];
      if (!used[v]) {
        used[v] = true;
        p[v] = u;
        dist[v] = dist[u] + 1;
        q.push(v);
      }
    }
  }
}

Здесь p — это массив предков, т.е. в p[v] лежит предок вершины v, dist[v] — это расстояние от вершины из которой мы начинали обход, до вершины v. Как восстановить путь? Это сделать довольно легко, просто пройдя по массиву предков нужной нам вершины. Например, рекурсивно:

void print_way(int u) {
  if (p[u] != u) {
    print_way(p[u]);
  }
  cout << u << ' ';
}

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

Кратчайшие пути

Теперь перейдем к взвешенным графам, т.е. ребра графа имеют вес. Например длина ребра. Или плата за проход по нему. Или время, которое требуется для прохода по нему. Задача — найти кратчайший путь из одной вершины, в какую-нибудь другую. В этой статье я буду отталкиваться от обхода в ширину, не помню, чтобы видел такой подход где-нибудь еще. Возможно я это пропустил. Итак, давайте посмотрим еще раз на реализацию обхода в ширину, а конкретно на условие добавления в очередь. В обходе в ширину мы добавляем в очередь только те вершины, в которых мы еще не были. Теперь же изменим это условие и будем добавлять те вершины, расстояние до которых можно уменьшить. Очевидно, что очередь опустеет тогда и только тогда, когда не останется ни одной вершины, до которой можно уменьшить расстояние. Процесс уменьшения пути из вершины V, назовем релаксацией вершины V. Следует заметить, что изначально путь до всех вершин равен бесконечности(за бесконечность возьмем какую-нибудь достаточно большую величину, а именно: такую, что ни один путь не будет иметь длины, большей величины бесконечности). Этот алгоритм напрямую следует из обхода в ширину, и именно до него я дошел сам, когда решал первую в жизни задачу на кратчайшие пути в графе. Стоит упомянуть, что такой способ ищет кратчайший пути от вершины, из которой мы начали алгоритм, до всех остальных. Приведу реализацию:

const int INF = 1e+9;

vector< pair<int, int> > g[LIM]; // В g[u] лежит список пар: (длина пути между вершиной u и v, вершина v)

void shortcut(int u) {
  fill(dist, dist + n, INF);
  dist[u] = 0;
  p[u] = u;
  queue<int> q;
  q.push(u);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = 0; i < (int) g[u].size(); i++) {
      int v = g[u][i].second, len = g[u][i].first;
      if (dist[v] > dist[u] + len) {
        p[v] = u;
        dist[v] = dist[u] + len;
        q.push(v);
      }
    }
  }
}

Почему храним в списке смежности именно такие пары? Чуть позже станет понятно, когда мы усовершенствуем этот алгоритм, но, честно говоря, для данной реализации пары можно хранить и наоборот. Можно немного улучшить добавление в очередь. Для этого стоит завести массив bool, в котором будем помечать, находится ли сейчас вершина, которою нужно прорелаксировать, в очереди.

const int INF = 1e+9;

vector< pair<int, int> > g[LIM];
bool inque[LIM];

void shortcut(int u) {
  fill(dist, dist + n, INF);
  dist[u] = 0;
  p[u] = u;
  queue<int> q;
  q.push(u);
  inque[u] = true;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    inque[u] = false;
    for (int i = 0; i < (int) g[u].size(); i++) {
      int v = g[u][i].second, len = g[u][i].first;
      if (dist[v] > dist[u] + len) {
        p[v] = u;
        dist[v] = dist[u] + len;
        if (!inque[v]) {
          q.push(v);
          inque[v] = true;
        }
      }
    }
  }
}

Если присмотреться, то этот алгоритм очень похож на алгоритм Левита, но все-таки это не он, хотя в худшем случае работает за ту же ассимтотику. Давайте грубо оценим это. В худшем случае нам придется проводить релаксацию каждый раз, когда мы проходим по какому-либо ребру. Итого O(n * m). Оценка довольно грубая, но на начальном этапе этого вполне хватит. Стоит так же заметить, что это именно худший случай, а на практике даже такая реализация работает довольно быстро. А теперь, самое интересное! ...барабанная дробь... Улучшим наш алгоритм до алгоритма Дейксты!

Алгоритм Дейкстры

Первая оптимизация, которая приходит на ум. А давайте релаксировать те вершины, путь до которой сейчас минимальный? Собственно, именно эта идея и пришла мне в один прекрасный день в голову. Но, как оказалось, эта идея пришла первому далеко не мне. Первому она пришла замечательному ученому Дейкстре. Более того, именно он доказал, что выбирая вершину для релаксации таким образом, мы проведем релаксацию не более, чем n раз! На интуитивном уровне понятно, что если до какой-то вершины путь сейчас минимальный, то еще меньше сделать его мы не сможем. Более формально можно прочитать на замечательном сайте e-maxx(Дружно говорим спасибо Максиму e-maxx Иванову) или на Википедии.
Теперь дело осталось за малым, понять как эффективно искать вершину с минимальным расстоянием до нее. Для этого воспользуемся очередью с приоритетами(куча, heap). В stl есть класс, который реализует ее и называется priority_queue. Приведу реализацию, которая, опять же, напрямую следует из предыдущего(описанного в этой статье) алгоритма.

void deikstra(int u) {
  fill(dist, dist + n, INF);
  dist[u] = 0;
  p[u] = u;
  priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > q;
  q.push(make_pair(0, u));
  while (!q.empty()) {
    pair<int, int> u = q.top();
    q.pop();
    if (u.first > dist[u.second]) continue;
    for (int i = 0; i < (int) g[u.second].size(); i++) {
      int v = g[u.second][i].second, len = g[u.second][i].first;
      if (dist[v] > dist[u.second] + len) {
        p[v] = u.second;
        dist[v] = dist[u.second] + len;
        q.push(make_pair(dist[v], v));
      }
    }
  }
}

Скорее всего не совсем понятно, что здесь происходит. Начнем с объявления очереди с приоритетами. Здесь первый аргумент шаблона — данные, которые хранятся в очереди, а конкретно пары вида (расстояние до вершины, номер вершины), второй аргумент шаблона — это контейнер, в котором будут храниться данные, третий аргумент, компоратор(находится, кстати, в заголовочном файле functional). Почему нам нужен какой-то другой компоратор? Потому что при стандартном обявлении priority_queue< pair<int, int> >, доставать получится только те вершины, расстояние до которых максимально, а нам-то нужно совсем наоборот. Есть и другой способ, который предлагает e-maxx, будем хранить отрицательные значения длин, а при вытаскивании длины из очереди умножать на -1(подробнее прочитать можно здесь). Ассимптотика такого решения поставленной задачи O(n * log(n) + m * log(n)). Действительно, всего у нас n релаксаций, а вершину с минимальной длиной пути до нее, мы ищем за log(n)(именно такая ассимптотика у стандартной очереди с приоритетами stl). Так же следует заметить, что у нас может получится так, что мы добавили в очередь одну и ту же вершину, но с разными путями до нее. Например, мы провели релаксацию из вершины A, у которой в соседях вершина C, а потом провели релаксацию из вершины B, у которой так же в соседях вершина C, для ухода от проблем, связанных с этим, будем просто пропускать те вершины, которые мы достали из очереди, но расстояние из очереди до которых не актуально, т.е. больше, чем текущее кратчайшее. Для этого в реализации присутствует строчка if (u.first > dist[u.second]) continue;.

Заключение

Оказалось, что на самом деле очень легко писать Дейкстру за O(n * log(n) + m * log(n))!

Я видимо совсем осел, но я такой фичи не нашел. Подскажите, пожалуйста, как это сделать? Или такой функционал отсутствует?

UPD. Решено. Смотрим первый комментарий в теме, если кому понадобится

Счастливые обладатели Google Chrome, Mozilla Firefox или Opera могут установить себе нехитрый userscript который убирает заглушку со страниц русскоязычной википедии. Пользователи IE, как всегда, прокляты.

(Не мой. Просто делюсь полезной штукой)

Доброе время суток.