E071. Обратная задача MST (inverse-MST - обратная задача минимального остова) за O (N M2)
Источник: e-maxx.ru/algo, страница PDF 210.
Дан взвешенный неориентированный граф G с N вершинами и M рёбрами (без петель и кратных рёбер). Известно, что граф связный. Также указан некоторый остов T этого графа (т.е. выбрано N-1 ребро, которые образуют дерево с N вершинами). Требуется изменить веса рёбер таким образом, чтобы указанный остов T являлся минимальным остовом этого графа (точнее говоря, одним из минимальных остовов), причём сделать это так, чтобы суммарное изменение всех весов было наименьшим.
Решение
Сведём задачу inverse-MST к задаче min-cost-flow, точнее, к задаче, двойственной min-cost-flow (в смысле двойственности задач линейного программирования); затем решим последнюю задачу. Итак, пусть дан граф G с N вершинами, M рёбрами. Вес каждого ребра обозначим через Ci. Предположим, не теряя общности, что рёбра с номерами с 1 по N-1 являются рёбрами T.
1. Необходимое и достаточное условие MST
Пусть дан некоторый остов S (не обязательно минимальный). Введём сначала одно обозначение. Рассмотрим некоторое ребро j, не принадлежащее S. Очевидно, в графе S имеется единственный путь, соединяющий концы этого ребра, т.е. единственный путь, соединяющий концы ребра j и состоящий только из рёбер, принадлежащих S. Обозначим через P[j] множество рёбер, образующих этот путь для j-го ребра. Для того, чтобы некоторый остов S являлся минимальным, необходимо и достаточно, чтобы:
Ci <= Cj для всех j ∉ S и каждого i ∈ P[j]
Можно заметить, что, поскольку в нашей задаче остову T принадлежат рёбра 1..N-1, то мы можем записать это условие таким образом:
Ci <= Cj для всех j = N..M и каждого i ∈ P[j]
(причём все i лежат в диапазоне 1..N-1)
2. Граф путей
Понятие графа путей непосредственно связано с предыдущей теоремой. Пусть дан некоторый остов S (не обязательно минимальный). Тогда графом путей H для графа G будет следующий граф:
● Он содержит M вершин, каждая вершина в H взаимно однозначно соответствует некоторому ребру в G.
● Граф H двудольный. В первой его доле находятся вершины i, которые соответствуют рёбрам в G, принадлежащим
остову S. Соответственно, во второй доле находятся вершины j, которые соответствуют рёбрам, не принадлежащим S.
● Ребро проводится из вершины i в вершину j тогда и только тогда, когда i принадлежит P[j].
Иными словами, для каждой вершины j из второй доли в неё входят рёбра из всех вершин первой доли, соответствующих множеству рёбер P[j]. В случае нашей задачи мы можем немного упростить описание графа путей: ребро (i,j) существует в H, если i ∈ P[j], j = N..M, i = 1..N-1
3. Математическая формулировка задачи
Чисто формально задача inverse-MST записывается таким образом:
найти массив A[1..M] такой, что
Ci + Ai <= Cj + Aj для всех j = N..M и каждого i ∈ P[j] (i в 1..N-1),
и минимизировать сумму |A1| + |A2| + ... + |Am|
здесь под искомым массивом A мы подразумеваем те значения, которые нужно добавить к весам рёбер (т.е., решив задачу inverse-MST, мы заменяем вес Ci каждого ребра i на величину Ci + Ai). Очевидно, что нет смысла увеличивать вес рёбер, принадлежащих T, т.е.
Ai <= 0, i = 1..N-1
и нет смысла укорачивать рёбра, не принадлежащие T:
Ai >= 0, i = N..M
(поскольку в противном случае мы только ухудшим ответ)
Тогда мы можем немного упростить постановку задачи, убрав из суммы модули:
найти массив A[1..M] такой, что
Ci + Ai <= Cj + Aj для всех j = N..M и каждого i ∈ P[j] (i в 1..N-1),
Ai <= 0, i = 1..N-1,
Ai >= 0, i = N..M,
и минимизировать сумму An + ... + Am - (A1 + ... + An-1)
Наконец, просто изменим "минимизацию" на "максимизацию", а в самой сумме изменим все знаки на противоположные:
найти массив A[1..M] такой, что
Ci + Ai <= Cj + Aj для всех j = N..M и каждого i ∈ P[j] (i в 1..N-1),
Ai <= 0, i = 1..N-1,
Ai >= 0, i = N..M,
и максимизировать сумму A1 + ... + An-1 - (An + ... + Am)
4. Сведение задачи inverse-MST к задаче, двойственной задаче
о назначениях
Формулировка задачи inverse-MST, которую мы только что дали, является формулировкой задачи линейного программирования с неизвестными A1..Am. Применим классический приём - рассмотрим двойственную ей задачу. По определению, чтобы получить двойственную задачу, нужно каждому неравенству сопоставить двойственную переменную Xij, поменять ролями целевую функцию (которую нужно было минимизировать) и коэффициенты в правых частях неравенств, поменять знаки "<=" на ">=" и наоборот, поменять максимизацию на минимизацию. Итак, двойственная к inverse-MST задача: найти все Xij для каждого (i,j) ∈ H, такие что:
все Xij >= 0,
для каждого i=1..N-1 ∑ Xij по всем j: (i,j) ∈ H <= 1,
для каждого j=N..M ∑ Xij по всем i: (i,j) ∈ H <= 1,
и минимизировать ∑ Xij (Cj - Ci) для всех (i,j) ∈ H
Последняя задача является задачей о назначениях: нам нужно в графе путей H выбрать несколько рёбер так, чтобы ни одно ребро не пересекалось с другим в вершине, а сумма весов рёбер (вес ребра (i,j) определим как Cj - Ci) должна быть наименьшей. Таким образом, двойственная задача inverse-MST эквивалентна задаче о назначениях. Если мы научимся решать двойственную задачу о назначениях, то мы автоматически решим задачу inverse-MST.
5. Решение двойственной задачи о назначениях
Сначала уделим немного внимания тому частному случаю задачи о назначениях, который мы получили. Во-первых, это несбалансированная задача о назначениях, поскольку в одной доле находится 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
Алгоритм начинает с нулевого потока, и нам нужно найти некоторые начальные значения потенциалов, которые бы удовлетворяли указанным условиям. Нетрудно проверить, что такой способ является одним из возможных решений:
PIj = 0 для j = N..M
PIi = min Cij, где (i,j) ∈ H
PIs = min PIi, где i = 1..N-1
PIt = 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];
... вывод графа ...
}
C# решение
auto-draft, проверить перед отправкойusing System;
using System.Collections.Generic;
using System.Linq;
public static class AlgorithmDraft
{
// Auto-generated C# draft from the original e-maxx C/C++ listing. Review before production use.
Ci <= Cj для всех j �∉ S и каждого i �∈ P[j]
Ci <= Cj для всех j = N..M и каждого i �∈ P[j]
(причём все i лежат в диапазоне 1..N-1)
ребро (i,j) существует в H, если i �∈ P[j], j = N..M, i = 1..N-1
найти массив A[1..M] такой, что
Ci + Ai <= Cj + Aj для всех j = N..M и каждого i �∈ P[j] (i в 1..N-1),
и минимизировать сумму |A1| + |A2| + ... + |Am|
Ai <= 0, i = 1..N-1
Ai >= 0, i = N..M
найти массив A[1..M] такой, что
Ci + Ai <= Cj + Aj для всех j = N..M и каждого i �∈ P[j] (i в 1..N-1),
Ai <= 0, i = 1..N-1,
Ai >= 0, i = N..M,
и минимизировать сумму An + ... + Am - (A1 + ... + An-1)
найти массив A[1..M] такой, что
Ci + Ai <= Cj + Aj для всех j = N..M и каждого i �∈ P[j] (i в 1..N-1),
Ai <= 0, i = 1..N-1,
Ai >= 0, i = N..M,
и максимизировать сумму A1 + ... + An-1 - (An + ... + Am)
найти все Xij для каждого (i,j) �∈ H, такие что:
все Xij >= 0,
для каждого i=1..N-1 ∑ Xij по всем j: (i,j) �∈ H <= 1,
для каждого j=N..M ∑ Xij по всем i: (i,j) �∈ H <= 1,
и минимизировать ∑ Xij (Cj - Ci) для всех (i,j) �∈ H
CPIij = Cij - PIi + PIj
если Fij = 0, то CPIij >= 0
если Fij = Uij, то CPIij <= 0
иначе CPIij = 0
PIj = 0 для j = N..M
PIi = min Cij, где (i,j) �∈ H
PIs = min PIi, где i = 1..N-1
PIt = 0
PIi -= Di
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 < List<int> > f (nn, List<int> (nn));
vector < List<int> > u (nn, List<int> (nn));
vector < List<int> > c (nn, List<int> (nn));
for (int i=n-1; i<m; ++i) {
List<int> q (n);
int h=0, t=0;
rib2 & cur = ribs[i];
q[t++] = cur.a;
List<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;
List<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 (;;) {
List<int> id (nn);
deque<int> q;
q.push_back (s);
List<int> d (nn, INF);
d[s] = 0;
List<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];
... вывод графа ...
}
}C++ решение
сопоставлено/оригиналCi <= Cj для всех j �∉ S и каждого i �∈ P[j]
Ci <= Cj для всех j = N..M и каждого i �∈ P[j]
(причём все i лежат в диапазоне 1..N-1)
ребро (i,j) существует в H, если i �∈ P[j], j = N..M, i = 1..N-1
найти массив A[1..M] такой, что
Ci + Ai <= Cj + Aj для всех j = N..M и каждого i �∈ P[j] (i в 1..N-1),
и минимизировать сумму |A1| + |A2| + ... + |Am|
Ai <= 0, i = 1..N-1
Ai >= 0, i = N..M
найти массив A[1..M] такой, что
Ci + Ai <= Cj + Aj для всех j = N..M и каждого i �∈ P[j] (i в 1..N-1),
Ai <= 0, i = 1..N-1,
Ai >= 0, i = N..M,
и минимизировать сумму An + ... + Am - (A1 + ... + An-1)
найти массив A[1..M] такой, что
Ci + Ai <= Cj + Aj для всех j = N..M и каждого i �∈ P[j] (i в 1..N-1),
Ai <= 0, i = 1..N-1,
Ai >= 0, i = N..M,
и максимизировать сумму A1 + ... + An-1 - (An + ... + Am)
найти все Xij для каждого (i,j) �∈ H, такие что:
все Xij >= 0,
для каждого i=1..N-1 ∑ Xij по всем j: (i,j) �∈ H <= 1,
для каждого j=N..M ∑ Xij по всем i: (i,j) �∈ H <= 1,
и минимизировать ∑ Xij (Cj - Ci) для всех (i,j) �∈ H
CPIij = Cij - PIi + PIj
если Fij = 0, то CPIij >= 0
если Fij = Uij, то CPIij <= 0
иначе CPIij = 0
PIj = 0 для j = N..M
PIi = min Cij, где (i,j) �∈ H
PIs = min PIi, где i = 1..N-1
PIt = 0
PIi -= Di
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];
... вывод графа ...
}Java решение
auto-draft, проверить перед отправкойimport java.util.*;
import java.math.*;
public class AlgorithmDraft {
// Auto-generated Java draft from the original e-maxx C/C++ listing. Review before production use.
Ci <= Cj для всех j �∉ S и каждого i �∈ P[j]
Ci <= Cj для всех j = N..M и каждого i �∈ P[j]
(причём все i лежат в диапазоне 1..N-1)
ребро (i,j) существует в H, если i �∈ P[j], j = N..M, i = 1..N-1
найти массив A[1..M] такой, что
Ci + Ai <= Cj + Aj для всех j = N..M и каждого i �∈ P[j] (i в 1..N-1),
и минимизировать сумму |A1| + |A2| + ... + |Am|
Ai <= 0, i = 1..N-1
Ai >= 0, i = N..M
найти массив A[1..M] такой, что
Ci + Ai <= Cj + Aj для всех j = N..M и каждого i �∈ P[j] (i в 1..N-1),
Ai <= 0, i = 1..N-1,
Ai >= 0, i = N..M,
и минимизировать сумму An + ... + Am - (A1 + ... + An-1)
найти массив A[1..M] такой, что
Ci + Ai <= Cj + Aj для всех j = N..M и каждого i �∈ P[j] (i в 1..N-1),
Ai <= 0, i = 1..N-1,
Ai >= 0, i = N..M,
и максимизировать сумму A1 + ... + An-1 - (An + ... + Am)
найти все Xij для каждого (i,j) �∈ H, такие что:
все Xij >= 0,
для каждого i=1..N-1 ∑ Xij по всем j: (i,j) �∈ H <= 1,
для каждого j=N..M ∑ Xij по всем i: (i,j) �∈ H <= 1,
и минимизировать ∑ Xij (Cj - Ci) для всех (i,j) �∈ H
CPIij = Cij - PIi + PIj
если Fij = 0, то CPIij >= 0
если Fij = Uij, то CPIij <= 0
иначе CPIij = 0
PIj = 0 для j = N..M
PIi = min Cij, где (i,j) �∈ H
PIs = min PIi, где i = 1..N-1
PIt = 0
PIi -= Di
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 < ArrayList<Integer> > f (nn, ArrayList<Integer> (nn));
vector < ArrayList<Integer> > u (nn, ArrayList<Integer> (nn));
vector < ArrayList<Integer> > c (nn, ArrayList<Integer> (nn));
for (int i=n-1; i<m; ++i) {
ArrayList<Integer> q (n);
int h=0, t=0;
rib2 & cur = ribs[i];
q[t++] = cur.a;
ArrayList<Integer> 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;
ArrayList<Integer> 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 (;;) {
ArrayList<Integer> id (nn);
deque<int> q;
q.push_back (s);
ArrayList<Integer> d (nn, INF);
d[s] = 0;
ArrayList<Integer> 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];
... вывод графа ...
}
}Материал разбит как алгоритмическая задача: изучить постановку, понять асимптотику и реализовать алгоритм на выбранном языке.
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.