e-maxx_algo

это несбалансированная задача о назначениях, поскольку в одной доле находится N-1 вершин, а в другой - M вершин, т.

е. в общем случае число вершин во второй доле больше на целый порядок. Для решения такой двойственной задачи

о назначениях есть специализированный алгоритм, который решит её за O (N3), но здесь этот алгоритм рассматриваться не будет. Во-вторых, такую задачу о назначениях можно назвать задачей о назначениях с взвешенными вершинами: веса рёбер положим равными 0, вес каждой вершины из первой доли положим равным -Ci,

из второй доли - равным Cj, и решение полученной задачи будет тем же самым.

Мы будем решать задачу двойственную задачу о назначениях с помощью модифицированного алгоритма min-cost-flow, который будет находить поток минимальной стоимости и одновременно решение двойственной задачи.

Свести задачу о назначениях к задаче min-cost-flow очень легко, но для полноты картины мы опишем этот процесс.

Добавим в граф исток s и сток t. Из s к каждой вершине первой доли проведём ребро с пропускной способностью = 1 и стоимостью = 0. Из каждой вершины второй доли проведём ребро к t с пропускной способностью = 1 и стоимостью = 0. Пропускные способности всех рёбер между первой и второй долями также положим равными 1.

Наконец, чтобы модифицированный алгоритм min-cost-flow (описанный ниже) работал, нужно добавить ребро из s в t с пропускной способностью = N+1 и стоимостью = 0.

6. Модифицированный алгоритм min-cost-flow для решения задачи о назначениях

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

Введём обозначения. Для каждого ребра (i,j) обозначим через Uij его пропускную способность, через Cij - его стоимость, через Fij - поток вдоль этого ребра.

Также введём понятие потенциалов. Каждая вершина обладает своим потенциалом PIi. Остаточная стоимость ребра CPIij определяется как:

CPIij = Cij - PIi + PIj

Влюбой момент работы алгоритма потенциалы таковы, что выполняются условия:

если Fij = 0, то CPIij >= 0 если Fij = Uij, то CPIij <= 0

иначе CPIij = 0

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

Собственно сам алгоритм min-cost-flow состоит из нескольких итераций. На каждой итерации мы находим кратчайший путь из s в t в остаточной сети, причём в качестве весов рёбер используем остаточные стоимости CPI. Затем мы увеличиваем поток вдоль найденного пути на единицу, и обновляем потенциалы следующим образом:

PIi -= Di

где Di - найденное кратчайшее расстояние от s до i (повторимся, в остаточной сети с весами рёбер CPI).

Рано или поздно мы найдём тот путь из s в t, который состоит из единственного ребра (s,t). Тогда после этой итерации нам следует завершить работу алгоритма: действительно, если мы не остановим алгоритм, то дальше уже будут находиться пути с неотрицательной стоимостью, и добавлять их в ответ не надо.

К концу работы алгоритма мы получим решение задачи о назначениях (в виде потока Fij) и решение двойственной задачи о назначениях (в массиве PIi).

(с PIi надо будет провести небольшую модификацию: от всех значений PIi отнять PIs, поскольку его значения имеют смысл только при PIs = 0)

6. Итог

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

Сначала мы должны будем построить граф путей. Для этого просто для каждого ребра j T обходом в ширину по остову T найдём путь P[j]. Тогда граф путей мы построим за O (M) * O (N) = O (N M).

Затем мы найдём начальные значения потенциалов за O (N) * O (M) = O (N M).

Затем мы будем выполнять итерации min-cost-flow, всего итераций будет не более N (поскольку из истока выходит N рёбер, каждое с пропускной способностью = 1), на каждой итерации мы ищем в графе путей кратчайшие пути от истока до всех остальных вершин. Поскольку вершин в графе путей равно M+2, а число рёбер - O (N M), то,

если реализовать поиск кратчайших путей простейшим вариантом алгоритма Дейкстры, каждая итерация min-cost- flow будет выполнять за O (M2), а весь алгоритм min-cost-flow выполнится за O (N M2).

Итоговая асимптотика алгоритма равна O (N M2).

Реализация

Реализуем весь вышеописанный алгоритм. Единственное изменение - вместо алгоритма Дейкстры применяется алгоритм Левита, который на многих тестах должен работать несколько быстрее.

const int INF = 1000*1000*1000;

struct rib {

int v, c, id;

};

struct rib2 {

int a, b, c;

};

int main() {

int n, m;

cin >> n >> m;

vector < vector<rib> > g (n); // граф в формате списков смежности vector<rib2> ribs (m); // все рёбра в одном списке

... чтение графа ...

int nn = m+2, s = nn-2, t = nn-1;

vector < vector<int> > f (nn, vector<int> (nn)); vector < vector<int> > u (nn, vector<int> (nn)); vector < vector<int> > c (nn, vector<int> (nn)); for (int i=n-1; i<m; ++i) {

vector<int> q (n); int h=0, t=0;

rib2 & cur = ribs[i]; q[t++] = cur.a; vector<int> rib_id (n, -1); rib_id[cur.a] = -2;

while (h < t) {

int v = q[h++];

for (size_t j=0; j<g[v].size(); ++j) if (g[v][j].id >= n-1)

break;

else if (rib_id [ g[v][j].v ] == -1) { rib_id [ g[v][j].v ] = g[v][j].id; q[t++] = g[v][j].v;

}

}

for (int v=cur.b, pv; v!=cur.a; v=pv) { int r = rib_id[v];

pv = v != ribs[r].a ? ribs[r].a : ribs[r].b; u[r][i] = n;

c[r][i] = ribs[i].c - ribs[r].c;

c[i][r] = -c[r][i];

}

}

u[s][t] = n+1;

for (int i=0; i<n-1; ++i) u[s][i] = 1;

for (int i=n-1; i<m; ++i) u[i][t] = 1;

vector<int> pi (nn); pi[s] = INF;

for (int i=0; i<n-1; ++i) { pi[i] = INF;

for (int j=n-1; j<m; ++j) if (u[i][j])

pi[i] = min (pi[i], ribs[j].c-ribs[i].c); pi[s] = min (pi[s], pi[i]);

}

for (;;) {

vector<int> id (nn); deque<int> q; q.push_back (s); vector<int> d (nn, INF); d[s] = 0;

vector<int> p (nn, -1); while (!q.empty()) {

int v = q.front(); q.pop_front(); id[v] = 2;

for (int i=0; i<nn; ++i)

if (f[v][i] < u[v][i]) {

int new_d = d[v] + c[v][i] - pi[v] +

pi[i];

if (new_d < d[i]) { d[i] = new_d; if (id[i] == 0)

q.push_back (i); else if (id[i] == 2)

q.push_front (i); id[i] = 1;

p[i] = v;

}

}

}

for (int i=0; i<nn; ++i) pi[i] -= d[i];

for (int v=t; v!=s; v=p[v]) { int pv = p[v]; ++f[pv][v], --f[v][pv];

}

if (p[t] == s) break;

}

for (int i=0; i<m; ++i) pi[i] -= pi[s];

for (int i=0; i<n-1; ++i) if (f[s][i])

ribs[i].c += pi[i]; for (int i=n-1; i<m; ++i)

if (f[i][t])

ribs[i].c += pi[i];

... вывод графа ...

}

Покраска рёбер дерева

Это достаточно часто встречающаяся задача. Дано дерево G. Поступают запросы двух видов: первый вид - покрасить некоторое ребро, второй вид - запрос количества покрашенных рёбер между двумя вершинами.

Здесь будет описано достаточно простое решение (с использованием дерева отрезков), которое будет отвечать на запросы за O (log N), с препроцессингом (предварительной обработкой дерева) за O (M).

Решение

Для начала нам придётся реализовать LCA, чтобы каждый запрос второго вида (i,j) сводить к двум запросам (a,b), где a - предок b.

Теперь опишем препроцессинг собственно для нашей задачи. Запустим поиск в глубину из корня дерева, этот поиск в глубину составит некоторый список посещения вершин (каждая вершина добавляется в список, когда поиск заходит в неё, и каждый раз после того, как поиск в глубину возвращается из сына текущей вершины) - кстати говоря, этот же список используется алгоритмом LCA. В этом списке будет присутствовать каждое ребро (в том смысле, что если i и j - концы ребра, то в списке обязательно найдётся место, где i и j идут подряд друг за

другом), причём присутствовать ровно 2 раза: в прямом направлении (из i в j, где вершина i ближе к корню, чем вершина j) и в обратном (из j в i).

Построим два дерева отрезков (для суммы, с единичной модификацией) по этому списку: T1 и T2. Дерево T1 будет учитывать каждое ребро только в прямом направлении, а дерево T2 - наоборот, только в обратном.

Пусть поступил очередной запрос вида (i,j), где i - предок j, и требуется определить, сколько рёбер покрашено на пути между i и j. Найдём i и j в списке обхода в глубину (нам обязательно нужны позиции, где они встречаются впервые), пусть это некоторые позиции p и q (это можно сделать за O (1), если вычислить эти позиции заранее во время препроцессинга). Тогда ответом будет сумма T1[p..q-1] - сумма T2[p..q-1].

Почему? Рассмотрим отрезок [p;q] в списке обхода в глубину. Он содержит рёбра нужного нам пути из i в j, но также содержит и множество рёбер, которые лежат на других путях из i. Однако между нужными нам рёбрами

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

обратном направлении. Следовательно, разность T1[p..q-1] - T2[p..q-1] даст нам ответ (минус один нужно, потому что иначе мы захватим ещё лишнее ребро из вершины j куда-то вниз или вверх). Запрос суммы в дереве

отрезков выполняется за O (log N).

Ответ на запрос вида 1 (о покраске какого-либо ребра) ещё проще - нам просто нужно обновить T1 и T2, а именно выполнить единичную модификацию того элемента, который соответствует нашему ребру (найти ребро в списке обхода, опять же, можно за O (1), если выполнить этот поиск в препроцессинге). Единичная модификация в дереве отрезков выполняется за O (log N).

Реализация

Здесь будет приведена полная реализация решения, включая LCA:

const int INF = 1000*1000*1000;

typedef vector < vector<int> > graph;

vector<int> dfs_list; vector<int> ribs_list; vector<int> h;

void dfs (int v, const graph & g, const graph & rib_ids, int cur_h = 1)

{

h[v] = cur_h; dfs_list.push_back (v);

for (size_t i=0; i<g[v].size(); ++i) if (h[g[v][i]] == -1)

{

ribs_list.push_back (rib_ids[v][i]); dfs (g[v][i], g, rib_ids, cur_h+1); ribs_list.push_back (rib_ids[v][i]); dfs_list.push_back (v);

}

}

vector<int> lca_tree;

vector<int> first;

void lca_tree_build (int i, int l, int r)

{

if (l == r)

lca_tree[i] = dfs_list[l];

else

{

int m = (l + r) >> 1; lca_tree_build (i+i, l, m); lca_tree_build (i+i+1, m+1, r);

int lt = lca_tree[i+i], rt = lca_tree[i+i+1]; lca_tree[i] = h[lt] < h[rt] ? lt : rt;

}

}

void lca_prepare (int n)

{

lca_tree.assign (dfs_list.size() * 8, -1); lca_tree_build (1, 0, (int)dfs_list.size()-1);

first.assign (n, -1);

for (int i=0; i < (int)dfs_list.size(); ++i)

{

int v = dfs_list[i];

if (first[v] == -1) first[v] = i;

}

}

int lca_tree_query (int i, int tl, int tr, int l, int r)

{

if (tl == l && tr == r) return lca_tree[i];

int m = (tl + tr) >> 1; if (r <= m)

return lca_tree_query (i+i, tl, m, l, r); if (l > m)

return lca_tree_query (i+i+1, m+1, tr, l, r); int lt = lca_tree_query (i+i, tl, m, l, m);

int rt = lca_tree_query (i+i+1, m+1, tr, m+1, r); return h[lt] < h[rt] ? lt : rt;

}

int lca (int a, int b)

{

if (first[a] > first[b]) swap (a, b);

return lca_tree_query (1, 0, (int)dfs_list.size()-1, first[a], first[b]);

}

vector<int> first1, first2; vector<char> rib_used; vector<int> tree1, tree2;

void query_prepare (int n)

{

first1.resize (n-1, -1); first2.resize (n-1, -1);

for (int i = 0; i < (int) ribs_list.size(); ++i)

{

int j = ribs_list[i]; if (first1[j] == -1) first1[j] = i;

else

first2[j] = i;

}

rib_used.resize (n-1);

tree1.resize (ribs_list.size() * 8); tree2.resize (ribs_list.size() * 8);

}

void sum_tree_update (vector<int> & tree, int i, int l, int r, int j, int delta)

{

tree[i] += delta; if (l < r)

{

int m = (l + r) >> 1; if (j <= m)

sum_tree_update (tree, i+i, l, m, j, delta);

else

sum_tree_update (tree, i+i+1, m+1, r, j, delta);

}

}

int sum_tree_query (const vector<int> & tree, int i, int tl, int tr, int l, int r)

{

if (l > r || tl > tr) return 0; if (tl == l && tr == r)

return tree[i]; int m = (tl + tr) >> 1; if (r <= m)

return sum_tree_query (tree, i+i, tl, m, l, r); if (l > m)

return sum_tree_query (tree, i+i+1, m+1, tr, l, r); return sum_tree_query (tree, i+i, tl, m, l, m)

+ sum_tree_query (tree, i+i+1, m+1, tr, m+1, r);

}

int query (int v1, int v2)

{

return sum_tree_query (tree1, 1, 0, (int)ribs_list.size()-1, first [v1], first[v2]-1)

- sum_tree_query (tree2, 1, 0, (int)ribs_list.size()-1, first[v1], first[v2]-1);

}

int main()

{

// чтение графа int n;

scanf ("%d", &n);

graph g (n), rib_ids (n); for (int i=0; i<n-1; ++i)

{

int v1, v2;

scanf ("%d%d", &v1, &v2); --v1, --v2; g[v1].push_back (v2); g[v2].push_back (v1); rib_ids[v1].push_back (i); rib_ids[v2].push_back (i);

}

h.assign (n, -1); dfs (0, g, rib_ids); lca_prepare (n); query_prepare (n);

for (;;) {

if () {

//запрос о покраске ребра с номером x;

//если start=true, то ребро красится,

иначе покраска снимается

rib_used[x] = start;

sum_tree_update (tree1, 1, 0, (int)ribs_list.size()- 1, first1[x], start?1:-1);

sum_tree_update (tree2, 1, 0, (int)ribs_list.size()- 1, first2[x], start?1:-1);

}

else {

//запрос кол-ва покрашенных рёбер на пути между v1 и v2 int l = lca (v1, v2);

int result = query (l, v1) + query (l, v2);

//result - ответ на запрос

}

}

}

Задача 2-SAT

Задача 2-SAT (2-satisfiability) - это задача распределения значений булевым переменным таким образом, чтобы они удовлетворяли всем наложенным ограничениям.

Задачу 2-SAT можно представить в виде конъюнктивной нормальной формы, где в каждом выражении в скобках стоит ровно по две переменной; такая форма называется 2-CNF (2-conjunctive normal form). Например:

(a || c) && (a || !d) && (b || !d) && (b || !e) && (c || d)

Приложения

Алгоритм для решения 2-SAT может быть применим во всех задачах, где есть набор величин, каждая из которых может принимать 2 возможных значения, и есть связи между этими величинами:

●Расположение текстовых меток на карте или диаграмме.

Имеется в виду нахождение такого расположения меток, при котором никакие две не пересекаются.

Стоит заметить, что в общем случае, когда каждая метка может занимать множество различных позиций, мы получаем задачу general satisfiability, которая является NP-полной. Однако, если ограничиться только двумя возможными позициями, то полученная задача будет задачей 2-SAT.

●Расположение рёбер при рисовании графа.

Аналогично предыдущему пункту, если ограничиться только двумя возможными способами провести ребро, то мы придём к 2-SAT.

●Составление расписания игр.

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

●и т.д.

Алгоритм

Сначала приведём задачу к другой форме - так называемой импликативной форме. Заметим, что выражение вида a || b эквивалентно !a => b или !b => a. Это можно воспринимать следующим образом: если есть выражение a || b, и

нам необходимо добиться обращения его в true, то, если a=false, то необходимо b=true, и наоборот, если b=false, то необходимо a=true.

Построим теперь так называемый граф импликаций: для каждой переменной в графе будет по две вершины, обозначим их через xi и !xi. Рёбра в графе будут соответствовать импликативным связям.

Например, для 2-CNF формы:

(a || b) && (b || !c)

Граф импликаций будет содержать следующие рёбра (ориентированные):

!a => b !b => a !b => !c c => b

Стоит обратить внимание на такое свойство графа импликаций, что если есть ребро a => b, то есть и ребро !b => !a.

Теперь заметим, что если для какой-то переменной x выполняется, что из x достижимо !x, а из !x достижимо x, то задача решения не имеет. Действительно, какое бы значение для переменной x мы бы ни выбрали, мы всегда придём к противоречию - что должно быть выбрано и обратное ему значение. Оказывается, что это условие является не только достаточным, но и необходимым (доказательством этого факта будет описанный ниже алгоритм). Переформулируем данный критерий в терминах теории графов. Напомним, что если из одной

вершины достижима другая, а из той вершины достижима первая, то эти две вершины находятся в одной сильно связной компоненте. Тогда мы можем сформулировать критерий существования решения следующим образом:

Для того, чтобы данная задача 2-SAT имела решение, необходимо и достаточно, чтобы для любой переменной x вершины x и !x находились в разных компонентах сильной связности графа импликаций.

Этот критерий можно проверить за время O (N + M) с помощью алгоритма поиска сильно связных компонент.

Теперь построим собственно алгоритм нахождения решения задачи 2-SAT в предположении, что решение существует. Заметим, что, несмотря на то, что решение существует, для некоторых переменных может выполняться, что из

x достижимо !x, или (но не одновременно), из !x достижимо x. В таком случае выбор одного из значений переменной x будет приводить к противоречию, в то время как выбор другого - не будет. Научимся выбирать из двух значений то, которое не приводит к возникновению противоречий. Сразу заметим, что, выбрав какое-либо значение, мы должны запустить из него обход в глубину/ширину и пометить все значения, которые следуют из него, т.е. достижимы

в графе импликаций. Соответственно, для уже помеченных вершин никакого выбора между x и !x делать не нужно, для

них значение уже выбрано и зафиксировано. Нижеописанное правило применяется только к непомеченным ещё вершинам.

Утверждается следующее. Пусть comp[v] обозначает номер компоненты сильной связности, которой принадлежит вершина v, причём номера упорядочены в порядке топологической сортировки компонент сильной связности в графе компонентов (т.е. более ранним в порядке топологической сортировки соответствуют большие

номера: если есть путь из v в w, то comp[v] <= comp[w]). Тогда, если comp[x] < comp[!x], то выбираем значение !x, иначе, т.

е. если comp[x] > comp[!x], то выбираем x.

Докажем, что при таком выборе значений мы не придём к противоречию. Пусть, для определённости, выбрана вершина x (случай, когда выбрана вершина !x, доказывается симметрично).

Во-первых, докажем, что из x не достижимо !x. Действительно, так как номер компоненты сильной связности comp [x] больше номера компоненты comp[!x], то это означает, что компонента связности, содержащая x, расположена левее компоненты связности, содержащей !x, и из первой никак не может быть достижима последняя.

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

x достижимо !x, что противоречит условию, что и требовалось доказать.

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

Теперь мы можем собрать весь алгоритм воедино:

●Построим граф импликаций.

●Найдём в этом графе компоненты сильной связности за время O (N + M), пусть comp[v] - это номер компоненты сильной связности, которой принадлежит вершина v.

●Проверим, что для каждой переменной x вершины x и !x лежат в разных компонентах, т.е. comp[x] ≠ comp[!x]. Если это условие не выполняется, то вернуть "решение не существует".

●Если comp[x] > comp[!x], то переменной x выбираем значение true, иначе - false.

Реализация

Ниже приведена реализация решения задачи 2-SAT для уже построенного графа импликаций g и обратного ему графа gt (т.е. в котором направление каждого ребра изменено на противоположное).

Программа выводит номера выбранных вершин, либо фразу "NO SOLUTION", если решения не существует.

int n;

vector < vector<int> > g, gt; vector<bool> used; vector<int> order, comp;

void dfs1 (int v) { used[v] = true;

for (size_t i=0; i<g[v].size(); ++i) { int to = g[v][i];

if (!used[to]) dfs1 (to);

}

order.push_back (v);

}

void dfs2 (int v, int cl) { comp[v] = cl;

for (size_t i=0; i<gt[v].size(); ++i) { int to = gt[v][i];

if (comp[to] == -1) dfs2 (to, cl);

}

}

int main() {

... чтение n, графа g, построение графа gt ...

used.assign (n, false);