- •1) Форд-Беллман
- •2) Флойд-Уоршелл
- •5) Алгоритм поиска компонент связности в графе
- •6) Поиск мостов
- •7) Поиск точек сочленения
- •8)Дейкстра
- •9) Эратосфен
- •10) Задача о назначениях
- •12)Эйлер
- •13) Binpow
- •14) Расширенный Евклид
- •15)Длинка
- •11) Алгоритм Куна нахождения наибольшего паросочетания в двудольном графе
- •16) Диофантовы уравнения
- •17) Нахождение степени делителя факториала
- •18) Дискретное логарифмирование
- •19) Нахождение площади простого многоугольника
- •20) Теорема Пика.
- •21) Пересечение окружности и прямой
- •22) Поиск общих касательных к двум окружностям
- •24) Префикс-функция. Алгоритм Кнута-Морриса-Пратта
- •25) Нахождение всех подпалиндромов
- •26) Максимальный подпалиндром
- •27) Нахождение наидлиннейшей возрастающей подпоследовательности
- •28) Динамика по профилю. Задача "паркет"
- •29) Нахождение наибольшей нулевой подматрицы
- •30) Гаусс
- •31) Интеграл по формуле Симпсона
- •32) Биномиальные коэффициенты
- •33) Числа Каталана
- •34) Ожерелья
- •35)Задача о ферзях
- •36)Ханойские башни
- •37) Правильные скобочные последовательности
- •38) Принцип включений-исключений
- •39) Теория Шпрага-Гранди. Ним
- •40) Оптимальный выбор заданий при известных временах завершения и длительностях выполнения
- •41) Игра Пятнашки: существование решения
- •42) Минимальное остовное дерево. Алгоритм Крускала
- •43) Количество всех остовов графа
- •44) Гамильтонов цикл
- •45) Задача о домино
- •46) Проверка на ацикличность и нахождение цикла
- •47) Топологическая сортировка
45) Задача о домино
Приведём здесь классическую задачу на эйлеров цикл - задачу о домино.
Имеется N доминошек, как известно, на двух концах доминошки записано по одному числу (обычно от 1 до 6, но в нашем случае не важно). Требуется выложить все доминошки в ряд так, чтобы у любых двух соседних доминошек числа, записанные на их общей стороне, совпадали. Доминошки разрешается переворачивать.
Переформулируем задачу. Пусть числа, записанные на донимошках, - вершины графа, а доминошки - рёбра этого графа (каждая доминошка с числами (a,b) - это ребра (a,b) и (b,a)). Тогда наша задача сводится к задаче нахожденияэйлерова пути в этом графе.
int main() {
int n;
vector < vector<int> > g (n, vector<int> (n));
... чтение графа в матрицу смежности ...
vector<int> deg (n);
for (int i=0; i<n; ++i)
for (int j=0; j<n; ++j)
deg[i] += g[i][j];
int first = 0;
while (!deg[first]) ++first;
int v1 = -1, v2 = -1;
bool bad = false;
for (int i=0; i<n; ++i)
if (deg[i] & 1)
if (v1 == -1)
v1 = i;
else if (v2 == -1)
v2 = i;
else
bad = true;
if (v1 != -1)
++g[v1][v2], ++g[v2][v1];
stack<int> st;
st.push (first);
vector<int> res;
while (!st.empty())
{
int v = st.top();
int i;
for (i=0; i<n; ++i)
if (g[v][i])
break;
if (i == n)
{
res.push_back (v);
st.pop();
}
else
{
--g[v][i];
--g[i][v];
st.push (i);
}
}
if (v1 != -1)
for (size_t i=0; i+1<res.size(); ++i)
if (res[i] == v1 && res[i+1] == v2 || res[i] == v2 && res[i+1] == v1)
{
vector<int> res2;
for (size_t j=i+1; j<res.size(); ++j)
res2.push_back (res[j]);
for (size_t j=1; j<=i; ++j)
res2.push_back (res[j]);
res = res2;
break;
}
for (int i=0; i<n; ++i)
for (int j=0; j<n; ++j)
if (g[i][j])
bad = true;
if (bad)
puts ("-1");
else
for (size_t i=0; i<res.size(); ++i)
printf ("%d ", res[i]+1);
}
46) Проверка на ацикличность и нахождение цикла
int n;
vector < vector<int> > g;
vector<char> cl;
vector<int> p;
int cycle_st, cycle_end;
bool dfs (int v) {
cl[v] = 1;
for (size_t i=0; i<g[v].size(); ++i) {
int to = g[v][i];
if (cl[to] == 0) {
p[to] = v;
if (dfs (to)) return true;
}
else if (cl[to] == 1) {
cycle_end = v;
cycle_st = to;
return true;
}
}
cl[v] = 2;
return false;
}
int main() {
... чтение графа ...
p.assign (n, -1);
cl.assign (n, 0);
cycle_st = -1;
for (int i=0; i<n; ++i)
if (dfs (i))
break;
if (cycle_st == -1)
puts ("Acyclic");
else {
puts ("Cyclic");
vector<int> cycle;
cycle.push_back (cycle_st);
for (int v=cycle_end; v!=cycle_st; v=p[v])
cycle.push_back (v);
cycle.push_back (cycle_st);
reverse (cycle.begin(), cycle.end());
for (size_t i=0; i<cycle.size(); ++i)
printf ("%d ", cycle[i]+1);
}
}
47) Топологическая сортировка
int n; // число вершин
vector<int> g[MAXN]; // граф
bool used[MAXN];
vector<int> ans;
void dfs (int v) {
used[v] = true;
for (size_t i=0; i<g[v].size(); ++i) {
int to = g[v][i];
if (!used[to])
dfs (to);
}
ans.push_back (v);
}
void topological_sort() {
for (int i=0; i<n; ++i)
used[i] = false;
ans.clear();
for (int i=0; i<n; ++i)
if (!used[i])
dfs (i);
reverse (ans.begin(), ans.end());
}
48)GCD and LCM
int gcd(int a,int b){
//return b ? gcd(b, a % b) : a;
if (b==0)
return a;
else
return gcd(b, a%b);
}
int lcm (int a, int b) {
return a*b / gcd(a, b);
}
Страница
