Category Archives: D. Графы

Алгоритмы на графах

Задачи на графах

Опубликовано: 18/05/2016

-= заготовка статьи =- Общим для задач на графах является необходимость их как-то хранить в программе. Для хранения графа [latex] G \left( V, E \right), |V| = n, |E| = m [/latex] в разных случаях используют различные методы. Наиболее популярны из них: Матрица смежности [latex] O \left( n^2 \right) [/latex] Матрица инцидентности [latex] O \left( … Continue reading →

e-olymp 3835. Минимальный каркас

13/07/2021 by Yezhkova

Задача

В связном графе найдите остовное дерево минимального веса.

Входные данные

Первая строка содержит два натуральных числа $n$ и $m$ $($$1 \leqslant n \leqslant 20000$, $0 \leqslant m \leqslant 100000$$)$ — количество вершин и рёбер графа соответственно. Следующие $m$ строк содержат описания рёбер по одному в строке. Ребро номер $i$ описывается тремя натуральными числами $b_i$, $e_i$ и $w_i$ $($$1 \leqslant b_i$, $e_i \leqslant n$, $0 \leqslant w_i \leqslant 100000$$)$ — номера концов ребра и его вес соответственно.

Граф является связным.

Выходные данные

Выведите единственное целое число — вес минимального остовного дерева.

Тесты

Входные данные	Выходные данные
4 4 1 2 1 2 3 2 3 4 5 4 1 4	7
10 10 1 3 1 1 4 5 1 2 6 2 3 5 2 5 3 3 4 5 3 5 6 3 6 4 6 4 2 6 5 6	15
7 12 1 2 20 1 7 1 1 6 23 6 7 36 2 7 4 2 3 15 7 3 9 6 5 28 7 5 25 3 4 3 4 5 17 4 7 16	57

Код программы

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;

int get(const int &n, int *&subtree) {
    if (subtree[n] == n) return n;
    return subtree[n] = get(subtree[n], subtree);  
}

void merge(const int &a, const int &b, int *&subtree, int *&vertex_rank) {
    int ra = get(a, subtree), rb = get(b, subtree);
    if (vertex_rank[ra] < vertex_rank[rb]) subtree[ra] = rb;
    else if (vertex_rank[rb] < vertex_rank[ra]) subtree[rb] = ra;
    else {
        subtree[ra] = rb;
        vertex_rank[rb]++;
    }
}

int main()
{
    int vertices, edges;
    scanf("%i%i", &vertices, &edges);
    vector <pair<int, pair<int, int>>> v(edges);
    for (int i = 0; i < edges; ++i) {
        scanf("%i%i%i", &v[i].second.first, &v[i].second.second, &v[i].first); 
    }
    sort(v.begin(), v.end());
    int *subtree = new int[vertices];
    int *vertex_rank = new int[vertices];
    for (int i = 0; i < vertices; i++) {
        subtree[i] = i;
        vertex_rank[i] = 1;
    }
    int spanning_tree_weight = 0;
    for (int i = 0; i < edges; ++i) {
        if (get(v[i].second.first - 1, subtree) != get(v[i].second.second - 1, subtree)) {
            spanning_tree_weight += v[i].first;
            merge(v[i].second.first - 1, v[i].second.second - 1, subtree, vertex_rank);
        }
    }
    printf("%i", spanning_tree_weight);
    delete[] subtree;
    delete[] vertex_rank;
    return 0;
}

#include <stdio.h>

#include <vector>

#include <algorithm>

#include <utility>

using namespace std;

int get(const int &n, int *&subtree) {

if (subtree[n] == n) return n;

return subtree[n] = get(subtree[n], subtree);

}

void merge(const int &a, const int &b, int *&subtree, int *&vertex_rank) {

int ra = get(a, subtree), rb = get(b, subtree);

if (vertex_rank[ra] < vertex_rank[rb]) subtree[ra] = rb;

else if (vertex_rank[rb] < vertex_rank[ra]) subtree[rb] = ra;

else {

subtree[ra] = rb;

vertex_rank[rb]++;

}

int main()

{

int vertices, edges;

scanf("%i%i", &vertices, &edges);

vector <pair<int, pair<int, int>>> v(edges);

for (int i = 0; i < edges; ++i) {

scanf("%i%i%i", &v[i].second.first, &v[i].second.second, &v[i].first);

}

sort(v.begin(), v.end());

int *subtree = new int[vertices];

int *vertex_rank = new int[vertices];

for (int i = 0; i < vertices; i++) {

subtree[i] = i;

vertex_rank[i] = 1;

}

int spanning_tree_weight = 0;

for (int i = 0; i < edges; ++i) {

if (get(v[i].second.first - 1, subtree) != get(v[i].second.second - 1, subtree)) {

spanning_tree_weight += v[i].first;

merge(v[i].second.first - 1, v[i].second.second - 1, subtree, vertex_rank);

}

printf("%i", spanning_tree_weight);

delete[] subtree;

delete[] vertex_rank;

return 0;

}

Решение задачи

Алгоритм

Задача решается алгоритмом Краскала. Для хранения данных удобно использовать вектор пар (одна пара = одна строка ввода). Пары в свою очередь состоят из двух элементов: пара вершин и вес ребра. Алгоритм Краскала предполагает сортировку рёбер по весу в порядке неубывания. Затем каждой вершине графа ставится в соответствие собственное поддерево. Удобно это сделать с помощью массива, элементов массива будет столько же, сколько и вершин. Далее нужно пройтись по всем рёбрам в порядке неубывания и определить, принадлежат ли вершины ребра $i$ одному и тому же поддереву. Если вершины находятся в разных поддеревьях, то эти поддеревья объединяются, а вес данного ребра дописывается в ответ.

Оптимизация

При помощи простого массива или вектора задача выполняется со сложностью $O(M log N + N^2)$, где $N$ — количество вершин, $M$ — количество рёбер. Система непересекающихся множеств (СНМ) позволяет добиться сложности $O(M log N)$. При поиске элемента в СНМ необходимо лишь подниматься вверх по деревьям, поэтому достаточно хранить для каждой вершины только номер её прямого предка. Для этого используется массив $subtree$. Для задания множества используется номер вершины — корня соответствующего дерева. Поэтому чтобы определить, принадлежат ли два элемента к одному и тому же множеству, для каждого элемента нужно найти корень соответствующего дерева (поднимаясь вверх пока это возможно) и сравнить эти корни. При поиске корня заданной вершины будем переподвешивать её за найденный корень при выходе из рекурсивной функции $get$. Пусть нам нужно объединить $(merge)$ множества с корнями $a$ и $b$. Присвоим $p[a]=b$, тем самым подвесив всё дерево $a$ к корню дерева $b$. Одна из самых простых и эффективных оптимизаций — поддерживать для всех деревьев текущую глубину, и при объединении подвешивать дерево с меньшей глубиной к корню дерева с большей глубиной. Глубина дерева данной вершины хранится в виде её ранга (массив $vertex$_$rank$).

Ссылки

Related Images:

e-olymp 1821. Comparing Answers

23/06/2021 by Yezhkova

Problem

In a place in Southwestern Europe, the name of which I do not wish to recall, not long ago there were $n$ cities connected by unidirectional roads, with possibly more than one road connecting a city to another one, or even to itself. As a homework assignment for your geography class, you need to calculate the number of paths of length exactly two that were between each pair of cities. However, you’ve been too busy celebrating the Spanish victory in the World Cup, so now you are copying the answers from your friend. You would like to make sure his answers are correct before handing in your homework.

Input

The input consists of several test cases, separated by single blank lines. Each test case begins with a line containing the integer $n$ $(1 \leqslant n \leqslant 1000)$. The following $n$ lines contain $n$ elements each, with element $j$ of line $i$ being the number of roads from city $i$ to city $j$ (a number between $0$ and $10$, inclusive). After that, there will be $n$ lines. Each will contain $n$ elements, with element $j$ of line $i$ being the answer from your friend for the number of length-$2$ paths from city $i$ to city $j$; it will be an integer between $0$ and $100000$ inclusive.

The test cases will finish with a line containing only the number zero (also preceded by a blank line).

Note: Large input file; use fast I/O routines.

Output

For each case, your program should output a line. The content of this line should be «YES» if your classmate’s solution to the assignment is right, and «NO» otherwise.

Tests

№	Input	Output
1	3 2 0 1 1 0 3 1 1 0 5 1 2 5 3 1 3 0 43 2 0 1 1 0 3 1 1 0 5 1 2 5 3 2 3 0 40	YES NO
2	5 1 2 7 8 9 4 5 8 7 3 1 0 2 5 6 1 0 0 5 4 1 7 2 5 9 33 75 55 142 170 42 54 90 157 154 14 44 23 73 95 10 30 15 53 65 45 100 85 137 1435 1 2 7 8 9 4 5 8 7 3 1 0 2 5 6 1 0 0 5 4 1 7 2 5 9 33 75 55 142 170 42 4 90 157 154 14 44 23 73 95 10 30 15 53 65 45 100 85 137 1430	YES NO
3	1 2 21 2 40	NO YES
4	9 1 5 7 9 10 6 3 3 6 10 2 0 5 10 4 3 3 5 7 10 4 1 4 0 4 4 2 5 4 0 1 7 0 5 3 2 7 0 6 1 7 5 2 2 2 7 4 0 1 1 8 6 6 3 0 4 9 2 1 8 0 3 7 8 7 7 3 5 0 10 8 2 1 0 5 8 8 8 3 3 1 287 178 173 129 293 196 195 180 134 182 123 203 174 287 214 150 143 144 202 143 163 158 261 150 126 128 148 125 78 153 108 182 137 82 89 109 156 141 157 108 183 149 120 120 105 166 145 166 147 192 199 157 161 147 207 159 98 105 176 141 159 149 81 243 232 270 182 300 197 184 192 201 213 152 128 61 176 142 160 147 1000	YES

Code

#define _CRT_SECURE_NO_WARNINGS // preprocessor property for Visual Studio
#include <stdio.h>
using namespace std;

inline void array_input(int **&arr, int &n) { // input function to avoid code repetition; it is optional
    for (int i = 0; i < n; ++i) {
        arr[i] = new int[n];
        for (int j = 0; j < n; ++j) {
            scanf("%d", &arr[i][j]);
        }
    }
}

inline void array_delete(int **&arr, int &n) { // array deletion to prevent memory leaks
    for (int i = 0; i < n; ++i) {
        delete[]arr[i];
    }
    delete[]arr;
}

int main()
{
    int n; // processing 1 testcase at a time
    while (scanf("%d", &n) && n) { // testcases are processed until the delimiter 0 occurs
        int **number_of_roads = new int *[n]; // array to square
        array_input(number_of_roads, n);
        int **friend_answers = new int *[n]; // array to compare calculated values to
        array_input(friend_answers, n);
        int correct_answer; // the actual number of length-2 routes isn't stored
        bool is_correct = true; // flag to stop calculation when error detected
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n && is_correct; ++j) { // if an error is detected the is_correct flag stops the cycle, if no error is detected j reaches n
                correct_answer = 0;
                for (int k = 0; k < n; ++k) {
                    correct_answer += number_of_roads[i][k] * number_of_roads[k][j]; // a single element of squared matrix 
                }
                if (friend_answers[i][j] != correct_answer) {
                    is_correct = false; // set the flag to stop calculation
                }
            }
        }
        printf(is_correct ? "YES\n" : "NO\n"); // output
        array_delete(number_of_roads, n);
        array_delete(friend_answers, n);
    }
    return 0;
}

#define _CRT_SECURE_NO_WARNINGS // preprocessor property for Visual Studio

#include <stdio.h>

using namespace std;

inline void array_input(int **&arr, int &n) { // input function to avoid code repetition; it is optional

for (int i = 0; i < n; ++i) {

arr[i] = new int[n];

for (int j = 0; j < n; ++j) {

scanf("%d", &arr[i][j]);

}

inline void array_delete(int **&arr, int &n) { // array deletion to prevent memory leaks

for (int i = 0; i < n; ++i) {

delete[]arr[i];

}

delete[]arr;

}

int main()

{

int n; // processing 1 testcase at a time

while (scanf("%d", &n) && n) { // testcases are processed until the delimiter 0 occurs

int **number_of_roads = new int *[n]; // array to square

array_input(number_of_roads, n);

int **friend_answers = new int *[n]; // array to compare calculated values to

array_input(friend_answers, n);

int correct_answer; // the actual number of length-2 routes isn't stored

bool is_correct = true; // flag to stop calculation when error detected

for (int i = 0; i < n; ++i) {

for (int j = 0; j < n && is_correct; ++j) { // if an error is detected the is_correct flag stops the cycle, if no error is detected j reaches n

correct_answer = 0;

for (int k = 0; k < n; ++k) {

correct_answer += number_of_roads[i][k] * number_of_roads[k][j]; // a single element of squared matrix

}

if (friend_answers[i][j] != correct_answer) {

is_correct = false; // set the flag to stop calculation

}

printf(is_correct ? "YES\n" : "NO\n"); // output

array_delete(number_of_roads, n);

array_delete(friend_answers, n);

}

return 0;

}

Solution

The problem statement says that element $j$ of line $i$ of the matrix corresponds to the number of unidirectional roads from city $i$ to city $j$. Thus, we have an adjacency matrix of a directed unweighted graph. We need to find the number of paths of fixed length $k = 2$ for each pair of cities and compare them to our friend’s answer from the output. Adjacency matrix $g_{n \times n}$ of a directed unweighted graph contains the number of routes of length $k = 1$ between each pair of vertices. The solution is iterative: adjacency matrix $g$ corresponds to paths of length $k = 1$. Let $g = d_k$. For $k + 1$ we have: $d_{k+1}[i][j] = \sum\limits_{p=1}^n d_k[i][p] \cdot g[p][j]$, i.e. the product of matrices $d_k$ and $g$. Conclusion: to count the routes of fixed length we have to raise the adjacence matrix to the correspondent power.

Testcases are processed one at a time and after each the answer is given. Firstly, two 2D arrays of size $n \times n$ are initialized and entered: one for storing the matrix with the amounts of paths and the other with our friend’s answers. There is a warning about a big input file in the problem statement. Thus we use C style for I/O operations. Secondly, the first matrix is squared and the results are compared to the friend’s answers one by one. Once an error is detected the loop ends and the answer «NO» is displayed. Otherwise the loop reaches its end and «YES» is displayed. It is necessary that both arrays are deleted before processing the next testcase to prevent memory leaks.

Links&References

Related Images:

e-olymp 7213. Шашка на кубе

12/12/2020 by Максим Ливитчук

Условие

Поверхность куба отрезками, параллельными рёбрам куба, разделена на квадратные клетки, длина сторон которых в $l$ (нечетное натуральное число) раз меньше длины ребра куба. Шашку передвигают за один ход из клетки на произвольную смежную с ней клетку (что имеет с данной общую сторону).

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

Входные данные

Содержит натуральные числа $l$ и $m$ ($l < 52$, $m < 200$).

Выходные данные

Вывести искомое количество способов.

Тесты

l	m	вывод
3	3	1
3	4	0
3	5	25
51	199	4009263689513240276071196173369495212494629453793821392879244551766927964742684514532573281589075237363501397360
3	199	11954860546705755218324706261555627152268568460810054501274297031890136116190373877274924800908756150285132065690107399

Код

#include <iostream>
#include <iomanip>
#include <vector>
using namespace std;

#define cr(a, b, x, y) case a: return CellCoord{b, x, y}
#define SIDENUM 3 //количество сторон куба которые хранятся
#define MAX_L 51 //максимальное значение L

#define BASE 1000000000 //10^9, основание системы счисления для длинной арифметики 
#define DNUM 9 //количество цифр 10-ичной системы счисления в 1 "цифре" длинной арифметики

struct LongNum {
    //реализация длинной арифметики на векторах со сложением и выводом
    vector<int> v;
    LongNum() {} //стандартный конструктор
    LongNum(int s) { //конструктор из int
        v.push_back(s);
    }
    void print() { //вывод числа
        cout <<(v.empty() ? 0 : v.back());
        for (int i = (int)v.size() - 2; i>=0; i--)
            cout <<setfill('0') <<setw(DNUM) <<v[i];
    }
    void add(LongNum term) { //прибавление длинного числа
        auto b = term.v;
        int carry = 0;
        for (size_t i = 0; i < max(v.size(), b.size()) || carry; i++) {
            if (i == v.size())
                v.push_back(0);
            v[i] += carry + (i < b.size() ? b[i] : 0);
            carry = v[i] >= BASE;
            if (carry)  v[i] -= BASE;
        }
    }
};

struct CellCoord {
    //хранит данные о положении клетки
    short side;
    short x, y;
};

struct CellNeighbors {
    //хранит данные о положении всех(4) соседей определённой клетки
    CellCoord n[4];
};

CellCoord FixNeighbor(short l, short side, short x, short y) {
    //исправляет данные о положении клетки, если она выходит за края грани
    if(x == -1) { //если сосед находится левее грани
        switch(side) {
        //если координаты выходят за левую границу 0-ой грани - меняет грань на 1-ую,
        //обнуляя y, а в x записывает старый y 
        cr(0, 1, y,     0); //и так далее
        cr(1, 1, l-1,   y);
        cr(2, 1, l-y-1, l-1);
        }
    } else if(x == l) {//правее
        switch(side) {
        cr(0, 1, l-y-1, 0);
        cr(1, 1, 0,     y);
        cr(2, 1, y,     l-1);
        }
    } else if(y == -1) {//выше
        switch(side) {
        cr(0, 1, l-x-1, 0);
        cr(1, 0, x,     l-1);
        cr(2, 1, x,     l-1);
        }
    } else if(y == l) {//ниже
        switch(side) {
        cr(0, 1, x,     0);
        cr(1, 2, x,     0);
        cr(2, 1, l-x-1, l-1);
        }
    } else {
        // если координаты не вышли за границы грани просто возвращаем неизменёные координаты
        return CellCoord{side, x, y};
    }
}

CellNeighbors GetNeighbors(short l, short side, short x, short y) {
    //возвращает исправленные координаты всех(4) соседних клеток
    return CellNeighbors{{
        FixNeighbor(l, side, x-1, y),
        FixNeighbor(l, side, x+1, y),
        FixNeighbor(l, side, x, y-1),
        FixNeighbor(l, side, x, y+1)
    }};
}

int main() {
    short l, m;
    bool flag = false;
    cin >>l >>m;
    LongNum cubes[2][SIDENUM][MAX_L][MAX_L];

    cubes[0][0][l/2][l/2] = LongNum(1);
    //за 0 ходов можно дойти 1 путём в изначальную точку

    CellNeighbors nbs[SIDENUM][MAX_L][MAX_L];
    //массив координат соседей

    for(short side=0; side<SIDENUM; side++) {
        for(short xi=0; xi<l; xi++) {
            for(short yi=0; yi<l; yi++) { //перебор координат всех клеток
                nbs[side][xi][yi] = GetNeighbors(l, side, xi, yi);
                //кэш координат соседних клеток
            }
        }
    }

    for(short i=0; i<m; i++) {
        for(short side=0; side<SIDENUM; side++) {
            for(short xi=0; xi<l; xi++) {
                for(short yi=0; yi<l; yi++) { //перебор всех клеток
                    LongNum neighbor_sum;
                    for(auto e: nbs[side][xi][yi].n) { //перебор всех соседей
                        neighbor_sum.add(cubes[flag][e.side][e.x][e.y]);
                        //сложение количества путей ко всем соседям на предыдущем шаге
                    }
                    cubes[!flag][side][xi][yi] = neighbor_sum;
                    //запись получившейся суммы в клетку
                }
            }
        }
        flag = !flag; //замена местами массива для предыдущего шага и нынешнего
    }
    cubes[flag][1][l/2][l/2].print();
    //вывод количества путей к центру соседней грани на m-ом шаге
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

#include <iostream>

#include <iomanip>

#include <vector>

using namespace std;

#define cr(a, b, x, y) case a: return CellCoord{b, x, y}

#define SIDENUM 3 //количество сторон куба которые хранятся

#define MAX_L 51 //максимальное значение L

#define BASE 1000000000 //10^9, основание системы счисления для длинной арифметики

#define DNUM 9 //количество цифр 10-ичной системы счисления в 1 "цифре" длинной арифметики

struct LongNum {

//реализация длинной арифметики на векторах со сложением и выводом

vector<int> v;

LongNum() {} //стандартный конструктор

LongNum(int s) { //конструктор из int

v.push_back(s);

}

void print() { //вывод числа

cout <<(v.empty() ? 0 : v.back());

for (int i = (int)v.size() - 2; i>=0; i--)

cout <<setfill('0') <<setw(DNUM) <<v[i];

}

void add(LongNum term) { //прибавление длинного числа

auto b = term.v;

int carry = 0;

for (size_t i = 0; i < max(v.size(), b.size()) || carry; i++) {

if (i == v.size())

v.push_back(0);

v[i] += carry + (i < b.size() ? b[i] : 0);

carry = v[i] >= BASE;

if (carry) v[i] -= BASE;

}

};

struct CellCoord {

//хранит данные о положении клетки

short side;

short x, y;

};

struct CellNeighbors {

//хранит данные о положении всех(4) соседей определённой клетки

CellCoord n[4];

};

CellCoord FixNeighbor(short l, short side, short x, short y) {

//исправляет данные о положении клетки, если она выходит за края грани

if(x == -1) { //если сосед находится левее грани

switch(side) {

//если координаты выходят за левую границу 0-ой грани - меняет грань на 1-ую,

//обнуляя y, а в x записывает старый y

cr(0, 1, y, 0); //и так далее

cr(1, 1, l-1, y);

cr(2, 1, l-y-1, l-1);

}

} else if(x == l) {//правее

switch(side) {

cr(0, 1, l-y-1, 0);

cr(1, 1, 0, y);

cr(2, 1, y, l-1);

}

} else if(y == -1) {//выше

switch(side) {

cr(0, 1, l-x-1, 0);

cr(1, 0, x, l-1);

cr(2, 1, x, l-1);

}

} else if(y == l) {//ниже

switch(side) {

cr(0, 1, x, 0);

cr(1, 2, x, 0);

cr(2, 1, l-x-1, l-1);

}

} else {

// если координаты не вышли за границы грани просто возвращаем неизменёные координаты

return CellCoord{side, x, y};

}

CellNeighbors GetNeighbors(short l, short side, short x, short y) {

//возвращает исправленные координаты всех(4) соседних клеток

return CellNeighbors{{

FixNeighbor(l, side, x-1, y),

FixNeighbor(l, side, x+1, y),

FixNeighbor(l, side, x, y-1),

FixNeighbor(l, side, x, y+1)

}};

}

int main() {

short l, m;

bool flag = false;

cin >>l >>m;

LongNum cubes[2][SIDENUM][MAX_L][MAX_L];

cubes[0][0][l/2][l/2] = LongNum(1);

//за 0 ходов можно дойти 1 путём в изначальную точку

CellNeighbors nbs[SIDENUM][MAX_L][MAX_L];

//массив координат соседей

for(short side=0; side<SIDENUM; side++) {

for(short xi=0; xi<l; xi++) {

for(short yi=0; yi<l; yi++) { //перебор координат всех клеток

nbs[side][xi][yi] = GetNeighbors(l, side, xi, yi);

//кэш координат соседних клеток

}

for(short i=0; i<m; i++) {

for(short side=0; side<SIDENUM; side++) {

for(short xi=0; xi<l; xi++) {

for(short yi=0; yi<l; yi++) { //перебор всех клеток

LongNum neighbor_sum;

for(auto e: nbs[side][xi][yi].n) { //перебор всех соседей

neighbor_sum.add(cubes[flag][e.side][e.x][e.y]);

//сложение количества путей ко всем соседям на предыдущем шаге

}

cubes[!flag][side][xi][yi] = neighbor_sum;

//запись получившейся суммы в клетку

}

flag = !flag; //замена местами массива для предыдущего шага и нынешнего

}

cubes[flag][1][l/2][l/2].print();

//вывод количества путей к центру соседней грани на m-ом шаге

}

Решение

Из условия можно понять, что задача про специфического вида граф, по которому движется шашка. Его вершинами являются клетки на гранях куба, а дуги лежат между клетками с общими границами. Очевидно количество путей за $m$ шагов до любой точки в графе будет равняться сумме количества путей за $m-1$ шагов ко всем соседним вершинам, то есть мы можем получать решение задачи для $m$ шагов из решения меньшей задачи для $m-1$ шагов, из чего можно понять что это задача на динамическое программирование.
Для решения создадим массив со всеми вершинами и будем хранить в нём количество путей к каждой из них на i-ом шаге. Удобнее всего задать такой массив как 6 числовых матриц размером $ l \times l$, по одной на каждую грань куба.

Раскладка шести граней куба с переходами между границами

Соседство будем определять, прибавляя или отнимая единицу от одной из координат клетки в матрице, например $(x-1, y)$ всегда будет соседом $(x, y)$, не считая крайних случаев, когда $x-1$ будет меньше нуля. Такие ситуации в коде обрабатывает функция FixNeighbor(...), в которой прописаны все подобные крайние случаи.

Если посмотреть на правильный ответ к пятому примеру, становится видно, что на больших значениях ответы на тесты превышают все стандартные целочисленные типы данных, поэтому для полного решения необходимо использовать длинную арифметику. В программе она реализована в виде структуры LongNum, логика работы которой взята отсюда.

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

Оптимизированный вариант хранения куба

Так как для получения значения клетки через $i$ шагов нужны значения всех её соседей через $i-1$ шагов, а для получения значения соседей через $i$ шагов нужно значение клетки через $i-1$ шагов, нам не хватит только одного массива для перезаписи, надо использовать минимум два для хранения предыдущего и нынешнего состояния. В программе это реализовано с помощью булевой переменной flag — сначала мы вычисляем следующее состояние на основании 0-ого массива ( flag), записывая результат 1-ый ( !flag), а потом инвертируем значение переменной на противоположное и массивы в алгоритме меняются местами.

Ссылки

Related Images:

e-olymp 7233. Путешествия в космосе

03/12/2020 by Євген Константинов

Задача

Инфраструктура космической галактики состоит из [latex]N[/latex] планет и [latex]M[/latex] прямых межпланетных маршрутов, каждый из которых связывает ровно две разные планеты. Расстояния в космосе достаточно большие, поэтому, если планеты не имеют прямого сообщения, то во время перелетов используют транзитные планеты.

Популярностью планеты [latex]k[/latex] будем считать количество пар различных планет [latex]i[/latex] и [latex]j[/latex], перелет между которыми возможен только при использовании планеты [latex]k[/latex] [latex] (i, j, k = 1..N)[/latex]. Для заданной системы космических сообщений найти значение максимальной популярности и количество планет, достигающих её.

Входные данные:

В первой строке натуральные числа [latex]N[/latex] и [latex]M[/latex] ([latex]1 \leqslant N \leqslant 1000[/latex], [latex]1 \leqslant M \leqslant 5000[/latex]). В следующих [latex]M[/latex] строках по два натуральных числа, описывающие маршрут между планетами [latex]i[/latex] и [latex]j[/latex] [latex](i, j, k = 1..N)[/latex].

Выходные данные:

Ответ к задаче.

Тесты

№	Входные данные	Выходные данные	Схема
1	4 4 1 2 1 3 1 4 2 3	5 1
2	14 14 1 2 2 3 2 4 3 5 1 6 6 7 7 8 8 6 1 9 9 10 10 11 9 12 1 13 13 14	75 1
3	4 4 1 2 2 3 3 4 4 1	3 4

Код

#include <iostream>
#include <vector>

using namespace std;

int inspect(int vertice, vector<int> graph[], bool visited[]);
bool allVisited(bool visited[], int n);
int firstNotVisited(bool visited[], int n);

int main() {
    int n, m, a, b;
    cin >> n >> m;
    
    vector<int> graph[n] = {};
    
    //Ввод данных, создание списка смежности графа
    
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        a--, b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    
    //Поиск наиболее популярного узла (планеты)
    //Осуществляется с помощью Depth-first search, поочередно убирая каждый узел
    //и перемножая кол-во планет в получившихся подграфах графа
    
    int maxPop = 0, maxPlanets = 0;
    for (int i = 0; i < n; i++) {
        bool visited[n] = {};
        //Отмечаем "убранный" узел как уже посещенный, чтобы не учитывать его при обходе
        visited[i] = true;
        vector<int> structures;
        //Рекурсивно проходим по всему графу, пока остаются не посещенные узлы
        //Кол-во итераций = кол-во подграфов
        while (!allVisited(visited, n))
            structures.push_back(inspect(firstNotVisited(visited, n), graph, visited));
        int pop = n - 1;
        //Изначальная популярность - кол-во других планет, т.к. перелет
        //между ними и убранной планетой уже не возможен
        for (int j = 0; j < structures.size() - 1; j++)
            for (int k = j + 1; k < structures.size(); k++)
                pop += structures[j] * structures[k];
                //Поочередно перемножаем кол-во планет из каждого подграфа
        if (pop > maxPop) {
            maxPlanets = 1;
            maxPop = pop;
        } else if (pop == maxPop)
            maxPlanets++;
    }
    cout << maxPop << " " << maxPlanets;
}

bool allVisited(bool visited[], int n) {
    for (int i = 0; i < n; i++)
        if (!visited[i]) return false;
    return true;
}

int firstNotVisited(bool visited[], int n) {
    for (int i = 0; i < n; i++)
        if (!visited[i]) return i;
    return -1;
}

int inspect(int vertice, vector<int> graph[], bool visited[]) {
    //Рекурсивный метод обхода графа
    //Проходится по всем смежным узлам из списка смежности, пока не наткнется
    //на уже посещенный узел
    int cnt = 1;
    visited[vertice] = true;
    for (auto e: graph[vertice])
        if (!visited[e])
            cnt += inspect(e, graph, visited);
    return cnt;
}

#include <iostream>

#include <vector>

using namespace std;

int inspect(int vertice, vector<int> graph[], bool visited[]);

bool allVisited(bool visited[], int n);

int firstNotVisited(bool visited[], int n);

int main() {

int n, m, a, b;

cin >> n >> m;

vector<int> graph[n] = {};

//Ввод данных, создание списка смежности графа

for (int i = 0; i < m; i++) {

cin >> a >> b;

a--, b--;

graph[a].push_back(b);

graph[b].push_back(a);

}

//Поиск наиболее популярного узла (планеты)

//Осуществляется с помощью Depth-first search, поочередно убирая каждый узел

//и перемножая кол-во планет в получившихся подграфах графа

int maxPop = 0, maxPlanets = 0;

for (int i = 0; i < n; i++) {

bool visited[n] = {};

//Отмечаем "убранный" узел как уже посещенный, чтобы не учитывать его при обходе

visited[i] = true;

vector<int> structures;

//Рекурсивно проходим по всему графу, пока остаются не посещенные узлы

//Кол-во итераций = кол-во подграфов

while (!allVisited(visited, n))

structures.push_back(inspect(firstNotVisited(visited, n), graph, visited));

int pop = n - 1;

//Изначальная популярность - кол-во других планет, т.к. перелет

//между ними и убранной планетой уже не возможен

for (int j = 0; j < structures.size() - 1; j++)

for (int k = j + 1; k < structures.size(); k++)

pop += structures[j] * structures[k];

//Поочередно перемножаем кол-во планет из каждого подграфа

if (pop > maxPop) {

maxPlanets = 1;

maxPop = pop;

} else if (pop == maxPop)

maxPlanets++;

}

cout << maxPop << " " << maxPlanets;

}

bool allVisited(bool visited[], int n) {

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

if (!visited[i]) return false;

return true;

}

int firstNotVisited(bool visited[], int n) {

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

if (!visited[i]) return i;

return -1;

}

int inspect(int vertice, vector<int> graph[], bool visited[]) {

//Рекурсивный метод обхода графа

//Проходится по всем смежным узлам из списка смежности, пока не наткнется

//на уже посещенный узел

int cnt = 1;

visited[vertice] = true;

for (auto e: graph[vertice])

if (!visited[e])

cnt += inspect(e, graph, visited);

return cnt;

}

Решение

Для начала представим полученный граф из планет в виде списка смежности (список, где каждой вершине соответствует список смежных ей других вершин). Так как нам надо получить значение наибольшей популярности, будем поочередно убирать (по сути заранее отмечать ее как посещенную) каждую из вершин и смотреть, между сколькими парами вершин нельзя составить маршрут. Для этого воспользуемся depth-first search. Его суть состоит в том, что мы берем любую вершину и начинаем рекурсивно проходить по всем ее соседям, а потом по их соседям и так далее. Каждую посещенную вершину мы отмечаем, чтобы при попадании на посещенную ранее вершину выйти из рекурсии. Таким образом, мы запускаем рекурсивную функцию пока остаются не посещенные вершины. В конце мы получим список связных подграфов и количество вершин в каждом из них. Чтобы получить популярность искомой вершины, мы суммируем кол-во остальных вершин (так как у них нет маршрута к убранной вершине) и поочередное произведение кол-ва вершин полученных подграфов.

Ссылки

Related Images:

e-olymp 9414. Убить всех термитов

21/12/2019 by Андрей Метасов

Условие задачи

На дереве живут термиты. Ваша задача убить их всех. Дерево является неориентированным связным графом с $n$ вершинами и $n — 1$ ребрами. Чтобы убить термитов, Вам следует отравить некоторые вершины. Если термит попадает на вершину с ядом, то он немедленно умирает. Вы не знаете, где изначально находятся термиты. Но Вы знаете, что термиты каждый раз попадают в случайную соседнюю вершину. Однако если термит прошел ребро $(u, v)$, то следующее ребро должно отличаться от $(v, u)$ за исключением случая, когда термит попадает в лист (в этом случае термит поворачивается и возвращается назад). Вам следует отравить минимальное количество вершин так, чтобы термиты попали в отравленные вершины после конечного числа шагов.

Входные данные

Первая строка содержит одно целое число $n$ $(1 \leqslant n \leqslant 100000)$. Следующая строка содержит $n — 1$ целое число $p_{i} (2 \leqslant i \leqslant n)$, означающее что ребро соединяет $p_{i}$ и $i$.

Выходные данные

Выведите минимальное количество отравленных вершин.

Тесты

№	Входные данные	Выходные данные
1	1	1
2	2 1	1
3	8 1 1 2 1 2 3 2	2
4	5 1 2 1 4	1
5	16 1 2 3 4 5 3 7 1 9 9 11 11 13 13 15	3
6	10 1 2 3 3 1 2 3 7 9	2
7	8 1 1 3 3 1 6 6	2

Код

#include <bits/stdc++.h>
using namespace std;

const int NMAX = 100001;
vector<int> tree [NMAX]; 
vector<int> killed (NMAX, 0);
vector<bool> used (NMAX, 0);
vector<int> dist (NMAX, 0);
int ans = 0;

void kills(int v, int p)
{
    if (v == p) kills(tree[v][0], v);
    if (tree[v].size() == 2) for (auto to : tree[v]) if (to != p) kills(to, v);
    if (tree[v].size() >= 3) killed[v]++;
    return;
}

void goup(int v, int p)
{
    if (v == p)
    {
        for (auto to : tree[v]) if (dist[to] < dist[v]) goup(to, v);
        killed[v] = 0;
        return;
    }
    if (tree[v].size() == 2) for (auto to : tree[v]) if (to != p) goup(to, v);
    if (tree[v].size() >= 3)
    {
        killed[v]++;
        return;
    }
}


int main()
{
    int n,v; cin>>n;
    if (n <= 5) {cout<<1; return 0;} // Частный случай
    tree[1].push_back(0); // Корень тоже должен быть "развилкой"
    vector<int> leaves;
    for (int i = 1; i < n; i++)
    {
        cin>>v;
        tree[v].push_back(i+1);
        tree[i+1].push_back(v); //Заполнение графа в том виде, в котором его дают
    }

    for (int i = 1; i <= n; i++)
    {
        if (tree[i].size() == 1 || (i == 1 && tree[i].size() == 2)) leaves.push_back(i); //Запоминаем все листья
    }

    queue<int> q; dist[1] = 0;
    q.push(1); used[1] = true;
    while (!q.empty())
    {
        int qv = q.front(); q.pop();
        used[qv] = 1;
        for (auto to : tree[qv])                //BFS заполняющий вектор dist
        {
            if (!used[to])
            {
                q.push(to);
                dist[to] = dist[qv]+1;
            }
        }
    }

    for (auto l : leaves)
    {
        kills(l, l);        // Первый этап - запросы от каждого листа
    }

    int maxdist = -1; for (int i = 1; i <= n; i++) maxdist = max(maxdist, dist[i]); // Определение максимального "уровня" дерева
    int wentup = 1;
    while (wentup)
    {
        wentup = 0;
        for (int l = maxdist; l > 0; l--)
        {
            for (int i = 2; i <= n; i++)
            {
                if (killed[i] == 1 && dist[i] == l)
                {
                    goup(i, i);                    //Этап 2 - поднятие "недошедших" запросов
                    wentup++;
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) if (killed[i] >= 2) ans++; //Финальный подсчет "отравленных" развилок
    cout<<ans;
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int NMAX = 100001;

vector<int> tree [NMAX];

vector<int> killed (NMAX, 0);

vector<bool> used (NMAX, 0);

vector<int> dist (NMAX, 0);

int ans = 0;

void kills(int v, int p)

{

if (v == p) kills(tree[v][0], v);

if (tree[v].size() == 2) for (auto to : tree[v]) if (to != p) kills(to, v);

if (tree[v].size() >= 3) killed[v]++;

return;

}

void goup(int v, int p)

{

if (v == p)

{

for (auto to : tree[v]) if (dist[to] < dist[v]) goup(to, v);

killed[v] = 0;

return;

}

if (tree[v].size() == 2) for (auto to : tree[v]) if (to != p) goup(to, v);

if (tree[v].size() >= 3)

{

killed[v]++;

return;

}

int main()

{

int n,v; cin>>n;

if (n <= 5) {cout<<1; return 0;} // Частный случай

tree[1].push_back(0); // Корень тоже должен быть "развилкой"

vector<int> leaves;

for (int i = 1; i < n; i++)

{

cin>>v;

tree[v].push_back(i+1);

tree[i+1].push_back(v); //Заполнение графа в том виде, в котором его дают

}

for (int i = 1; i <= n; i++)

{

if (tree[i].size() == 1 || (i == 1 && tree[i].size() == 2)) leaves.push_back(i); //Запоминаем все листья

}

queue<int> q; dist[1] = 0;

q.push(1); used[1] = true;

while (!q.empty())

{

int qv = q.front(); q.pop();

used[qv] = 1;

for (auto to : tree[qv]) //BFS заполняющий вектор dist

{

if (!used[to])

{

q.push(to);

dist[to] = dist[qv]+1;

}

for (auto l : leaves)

{

kills(l, l); // Первый этап - запросы от каждого листа

}

int maxdist = -1; for (int i = 1; i <= n; i++) maxdist = max(maxdist, dist[i]); // Определение максимального "уровня" дерева

int wentup = 1;

while (wentup)

{

wentup = 0;

for (int l = maxdist; l > 0; l--)

{

for (int i = 2; i <= n; i++)

{

if (killed[i] == 1 && dist[i] == l)

{

goup(i, i); //Этап 2 - поднятие "недошедших" запросов

wentup++;

}

for (int i = 1; i <= n; i++) if (killed[i] >= 2) ans++; //Финальный подсчет "отравленных" развилок

cout<<ans;

return 0;

}

Решение задачи

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

Определим для этого $3$ типа вершин: лист, развилка и обычная вершина. Листом назовем вершину, у которой нет детей (всего $1$ связь с другой вершиной). Обычные вершины — те, у которых ровно $2$ связи (для нашего термита это пути вниз или вверх). Развилкой назовем вершину, у которой $3$ или больше связей с другими. Будем считать корень тоже развилкой, даже если у него всего $2$ связи, или листом, если одна. Через развилки можно ходить из одного листа в другой, либо «вверх» — в сторону корня.

$1$ — корень; $5,6,3$ — листья; $4$ — развилка; $2$ — обычная;

Первый этап

Очевидно, выгоднее всего «закрывать» развилки. А среди них — те, которые соединяют несколько листов напрямую. Пусть каждый лист отправляет «запрос» вверх по дереву на закрытие ближайшей к нему развилки. Когда «запрос» доходит до развилки, он тут же записывается на её счёт. Таким образом, в дереве выше вершина $4$ будет иметь $2$ запроса — от листов $5$ и $6$, а корень — $1$ запрос от листа $3$.

Теперь, просто считаем количество вершин с количеством запросов $\geqslant2$ и «закрываем» их.

Второй этап

Увы, первый этап не идеален и может «не донести» запросы в нужное место, т.к. некоторые развилки (а именно — соединяющие лист и другую развилку) могут остаться с одним запросом и не быть закрытыми. Если таких много, термит все еще может ходить между листами. Например, в таком дереве:

Дерево, в котором необходим второй этап

Вершина $2$ и корень получают по $1$ запросу и остаются открытыми, а у термита остается путь между листами $10$ и $6$.

Для предотвращения таких случаев, пробежимся по дереву «снизу вверх» — от самого нижнего уровня до верхнего и для каждой развилки, у которой ровно $1$ запрос, сместим его вверх аналогично первому этапу — до ближайшей развилки. Будем выполнять этот шаг, пока есть такие вершины (с $1$ запросом).

В итоге, все запросы «соединятся» в нужных развилках, значение в них станет $\geqslant2$ и эти развилки нужно будет тоже закрыть. Для дерева выше, будет закрыт корень.

Осталось посчитать кол-во закрытых.

Описание алгоритма

Дерево будем хранить в массиве векторов tree. Количество запросов для вершины $i$ хранится в killed[i]. Стандартный вектор used для поиска в ширину и dist- вектор расстояний от корня до вершин, которые и будут определяться с помощью BFS.

Функция kills предназначена для того, чтобы донести запрос от листа до развилки. Она рассматривает $3$ случая:

v == p — текущая вершина совпадает с той, из которой пришли. Это крайний случай, говорящий о том, что мы только начали и находимся в листе. Тогда, идем в единственно возможном направлении — tree[v][0].
tree[v].size == 2 — вершина обычного типа, просто идем «вверх», выбирая из двух путей тот, что не совпадает с предыдущей вершиной.
tree[v].size >= 3 — попали в развилку. Увеличиваем ее значение killed[v] и выходим из рекурсии.

Функция goup отличается от kills лишь тем, что при v == p выбирает из всех направлений то, которое ближе к корню, используя dist.

Подготовка

Можно заметить, что для всех деревьев из $5$ или менее вершин ответ будет $1$. Проверим это сразу при вводе n. Далее, осторожно считываем дерево в массив векторов (см. Входные данные). В следующем цикле, определяем листья и запоминаем их в вектор leaves. Нужно учесть то, что корень может быть листом, если у него всего $2$ связи — одна с деревом, а другая — искусственно созданная нами в $0$ вершину. Последний шаг — запустить поиск в ширину из корня, который заполнит вектор dist расстояниями от корня до вершин.

Первый этап

Просто запускаем kills (l, l) из каждого листа l для «отправки» запросов в ближайшие развилки.

Второй этап

Определяем максимальную «глубину» дерева — максимальное расстояние вершины от корня. Далее, для каждого уровня от самого нижнего до корня, при определении вершины со значением killed[i] == 1 запускаем goup (i, i), а в переменной wentup считаем количество таких случаев. Как только их не останется — while выйдет из цикла.

Наконец, осталось просто посчитать количество вершин, у которых значение killed[i] >= 2.
Задача на e-olymp
Код решения на ideone
Засчитанное решение на e-olymp

Related Images:

e-olymp 1390. Автогонки

18/12/2019 by Владимир Захаренко

Задача

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

В городе $N$ есть $n$ перекрёстков, некоторые пары которых соединены дорогами, движение по которым возможно в обоих направлениях. При этом любые два перекрёстка соединены не более чем одной дорогой, и есть возможность доехать по дорогам от любого перекрёстка до любого другого.

Трасса, на которой будут проводится соревнования, должна быть круговой (т.е. должна начинаться и заканчиваться на одном и том же перекрёстке), при этом в процессе движения по ней никакой перекрёсток не должен встречаться более одного раза.

На предварительном этапе подготовки оргкомитетом был создан список всех дорог города. Теперь настало время его использовать. Первый вопрос, который необходимо решить, — это вопрос о существовании в городе требуемой круговой трассы (разумеется, если ответ будет отрицательным, организаторам придётся в срочном порядке построить ещё несколько дорог). Единственная проблема заключается в том, что у организаторов есть подозрение, что, поскольку список составлялся не очень внимательно, в нём некоторые дороги указаны более одного раза.

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

Входные данные

Первая строка содержит два целых числа: количество перекрёстков $n$ $(1 \leqslant n \leqslant 1000)$ в городе $N$ и количество дорог $m$ $(0 \leqslant m \leqslant 100000)$ в составленном списке.

Последующие $m$ строк описывают дороги. Каждая дорога описывается двумя числами: $u$ и $v$ $(1 \leqslant u, v \leqslant n, u ≠ v)$ — номера перекрёстков, которые она соединяет. Так как дороги двусторонние, то пара чисел $(u, v)$ и пара чисел $(v, u)$ описывают одну и ту же дорогу.

Выходные данные

Вывести YES, если в городе возможно организовать круговую трассу для соревнований, и слово NO в противном случае.

Тесты

Входные данные	Выходные данные
3 4 1 2 2 3 3 1 3 2	YES
2 3 1 2 2 1 2 1	NO
8 10 1 4 4 7 7 8 5 6 1 5 6 7 4 1 4 3 2 3 1 5	YES
6 5 4 2 1 2 2 3 2 5 5 6	NO
8 8 1 5 1 6 4 7 8 4 1 3 2 1 4 1 5 6	YES
8 12 8 5 4 3 4 6 4 1 2 4 2 3 4 3 5 1 5 7 7 6 4 2 1 2	YES

Код программы

#include <iostream>
#include <vector>
using namespace std;

enum color_t {
    WHITE, GRAY, BLACK // Вводим тип данных, отвечающий за цвет вершины
};

vector<color_t> color; // Список, в котором указаны цвета всех вершин
vector<vector<int>> crossroads; // Списки смежности перекрестков

bool is_track(int crossroad, int parent) { // Функция, проверяющая наличие круговой трассы
    if(color[crossroad] == GRAY) return true; // Условие существования цикла
    color[crossroad] = GRAY;
    for(auto next_crossroad : crossroads[crossroad]) { // Переход в соседние вершины
        if(parent != next_crossroad && is_track(next_crossroad, crossroad)) return true; // Вход в вершину, которую еще не входили
    }
    color[crossroad] = BLACK; // Если далее нет цикла, окрашиваем вершину в черный
    return false;
}

int main() {
    int n, m; // Количество перекрестков и дорог
    cin >> n >> m;
    crossroads.resize(n);color.resize(n, WHITE); // Окрашиваем все вершины в белый цвет
    for(int i = 0; i < m; i++) {
        int u, v; // Номер перекрестков, соединенных дорогой
        cin >> u >> v;
        u--;v--; // Так как по условию отсчёт начинается с первой вершины, вычитаем 1 для удобства
        bool already_road = false; // Проверяем, не повторяется ли дорога
        if(!crossroads[u].empty() && !crossroads[v].empty()) {
            int number_of_neighbours = crossroads[u].size();
            for(int j = 0; j < number_of_neighbours && already_road == false; j++) {
                if(crossroads[u][j] == v) already_road = true;
            }
        }
        if(!(already_road)) { // Проверка на повторение
            crossroads[u].push_back(v); // Добавляем в список доступных перекрестков перекрестка u перекресток v
            crossroads[v].push_back(u); // Аналогичные действия для перекрестка v, чтобы учесть возможность двусторонней езды
        }
    }
    cout << (is_track(0, 0) ? "YES" : "NO"); // Запускаем функцию поиска круговой трассы с первого перекрестка и выводим ответ
}

#include <iostream>

#include <vector>

using namespace std;

enum color_t {

WHITE, GRAY, BLACK // Вводим тип данных, отвечающий за цвет вершины

};

vector<color_t> color; // Список, в котором указаны цвета всех вершин

vector<vector<int>> crossroads; // Списки смежности перекрестков

bool is_track(int crossroad, int parent) { // Функция, проверяющая наличие круговой трассы

if(color[crossroad] == GRAY) return true; // Условие существования цикла

color[crossroad] = GRAY;

for(auto next_crossroad : crossroads[crossroad]) { // Переход в соседние вершины

if(parent != next_crossroad && is_track(next_crossroad, crossroad)) return true; // Вход в вершину, которую еще не входили

}

color[crossroad] = BLACK; // Если далее нет цикла, окрашиваем вершину в черный

return false;

}

int main() {

int n, m; // Количество перекрестков и дорог

cin >> n >> m;

crossroads.resize(n);color.resize(n, WHITE); // Окрашиваем все вершины в белый цвет

for(int i = 0; i < m; i++) {

int u, v; // Номер перекрестков, соединенных дорогой

cin >> u >> v;

u--;v--; // Так как по условию отсчёт начинается с первой вершины, вычитаем 1 для удобства

bool already_road = false; // Проверяем, не повторяется ли дорога

if(!crossroads[u].empty() && !crossroads[v].empty()) {

int number_of_neighbours = crossroads[u].size();

for(int j = 0; j < number_of_neighbours && already_road == false; j++) {

if(crossroads[u][j] == v) already_road = true;

}

if(!(already_road)) { // Проверка на повторение

crossroads[u].push_back(v); // Добавляем в список доступных перекрестков перекрестка u перекресток v

crossroads[v].push_back(u); // Аналогичные действия для перекрестка v, чтобы учесть возможность двусторонней езды

}

cout << (is_track(0, 0) ? "YES" : "NO"); // Запускаем функцию поиска круговой трассы с первого перекрестка и выводим ответ

}

Объяснение

По условию ясно, что нам необходимо создать неориентированный граф с $n$ вершинами. Ребрами в созданном графе являются дороги, соединяющие по два перекрестка каждая. Сам граф можно записать с помощью списков смежности. Во входных данных может быть записана одна и та же дорога по несколько раз. Это никак не скажется на результате программы, но будет использовано больше памяти в сравнении с тем вариантом, если их проигнорировать. Достаточно проверить в списке первой вершины наличие второй, чтобы не учитывать повторения.

Круговая трасса в городе представляет в структуре графа представляется циклом. Для его поиска можно использовать обход в глубину (DFS). Обход можно начинать с любой вершины, ведь от этого результат не зависит. Для определенности в коде, указанном выше, обход начинается с нулевой (в самой задаче с первой). Для вершин также введем дополнительную характеристику. Назовем не посещенную вершину белой (WHITE), посещенную — серой (GRAY). Вершину, из которой более некуда идти, обозначим черной (BLACK). Также вершину, из которой мы пришли, назовем родителем. При заходе в граф каждая вершина является белой. При входе в вершину мы проверяем, не является ли она серой. Если да, то это означает, что мы нашли цикл, и можем заканчивать обход и выводить YES. Если вершина является белой, то она окрашивается в серый. Далее из нее идет переход в доступную вершину из данной, кроме родителя. В следующей вершине повторяются все прошлые действия. Если из вершины больше нельзя никуда пойти, кроме как назад, то она становится черной и совершается возврат в родителя. И, наконец, если все вершины — черные, то цикла нет. Значит можно заканчивать обход и выводить NO.

Ссылки

Условие на e-olymp
Код задачи на Ideone

Related Images:

e-olymp 34. Слово спонсора

06/12/2019 by Артем Рогулин

Задача

По завершению турнира «Новогодняя ночь» спонсор решил отправить $m$ призерам подарки по почте. Зная количество участников $n$ и время доставки почты между некоторыми отделениями «Укрпочты», найти, через какое минимальное время последний из призеров получит свой приз.

Входные данные

Первая строка содержит $3$ числа: количество участников турнира $n$, количество призов спонсора $m$ и количество известных временных сроков доставки между некоторыми из отделений $k$. В следующей строке через пробел указаны номера участников, ставших призёрами.

Далее идет $k$ строк по $3$ числа в каждой с информацией об известных сроках доставки между некоторыми из отделений в формате: $a$ $b$ $t$, где $a$ и $b$ — номера отделений, $t$ $(0 \leqslant t \leqslant 365)$ — время доставки почты между ними. В последней строке находится единственное число — номер почтового отделения, из которого спонсор будет отправлять призы. Известно, что $1 \leqslant n, m, a, b \leqslant 365$.

Выходные данные

Если все призы будут доставлены участникам — вывести в первой строке «The good sponsor!», а в следующей — время, через какое последний из призеров получит свой приз. Если хотя бы один из участников не сможет получить приз — вывести в единственной строке «It is not fault of sponsor…». Фразы выводить без кавычек.

Тесты

№	Входные данные	Выходные данные
1.	3 2 2 2 3 1 2 3 2 3 4 1	The good sponsor! 7
2.	5 1 4 5 1 3 2 2 3 3 4 2 5 4 5 6 1	The good sponsor! 16
3.	7 2 6 1 3 1 3 2 2 4 32 4 5 94 3 1 0 6 2 4 7 2 3 7	It is not fault of sponsor…
4.	5 2 6 1 2 3 1 1 3 4 2 2 4 3 5 1 4 4 5 5 2 3 7 2	The good sponsor! 6

Код программы

Первый вариант

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    int n, m, k; // Количество вершин, количество победителей и количество ребер
    cin >> n >> m >> k;
    vector<int> winner(m); // Вершины, которые нам нужно достичь
    for(int i = 0; i < m; i++) 
    {
        cin >> winner[i];
        winner[i]--; // В задаче отсчёт идёт с 1, поэтому мы уменьшаем все индексы на 1
    }
    vector<vector<vector<int>>> path(n); // Список смежности с весом
    for(int i = 0; i < k; i++)
    {
        int a, b, t;
        cin >> a >> b >> t; // Соединённые вершины и вес ребра
        a--;// Сдвиг индексов на 1
        b--;
        path[a].push_back({b, t}); // В список путей из вершины 'а' добавляем вершину 'b' и длину пути
        path[b].push_back({a, t}); 
    }
    int start; // Вершина, с которой мы начинаем
    cin >> start;
    start--; // Сдвигаем индекс
    vector<int> count(n, -1); // Счётчик длины путей
    count[start] = 0; // Мы находимся в этой вершине, поэтому дистанция до неё равна 0
    queue<int> plan; // Наш план посещения вершин. Так как мы используем BFS, то это контейнером является очередь
    plan.push(start); // Кладём нашу стартовую вершину в план
    while(!plan.empty()) // Наш BFS
    {
        start = plan.front(); 
        plan.pop();
        for(auto next: path[start]) // Достаём наши пары  вершина + вес
        {
            if(count[next[0]] == -1 || count[next[0]] > count[start] + next[1]) // Если вершина не посещена или путь через ту на котором мы сейчас более короткий
            {
                plan.push(next[0]); // Мы добавляем эту вершину в план
                count[next[0]] = count[start] + next[1]; // И отмечаем дистанцию до неё
            }
        }
    }
    bool delivered = true; // Предпологаем, что мы побывали во всех вершинах, которые нам нужны
    int longest = 0; // Положим максимальную дистанцию равной нулю
    for(int i = 0; i < m && delivered; i++)
    {
        if(count[winner[i]] == -1) // Если путь до нужной вершины не был найден
        {
            delivered = false; // Отмечаем, что мы побывали не везде, где надо
        }
        longest = max(count[winner[i]], longest);
    }
    if(delivered) // Если нужные вершины посещены
    {
        cout << "The good sponsor!\n" << longest; // Выводим фразу и длину пути до самой далёкой вершины
    }
    else
    {
        cout << "It is not fault of sponsor...";
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <queue>

using namespace std;

int main() {

int n, m, k; // Количество вершин, количество победителей и количество ребер

cin >> n >> m >> k;

vector<int> winner(m); // Вершины, которые нам нужно достичь

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

{

cin >> winner[i];

winner[i]--; // В задаче отсчёт идёт с 1, поэтому мы уменьшаем все индексы на 1

}

vector<vector<vector<int>>> path(n); // Список смежности с весом

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

{

int a, b, t;

cin >> a >> b >> t; // Соединённые вершины и вес ребра

a--;// Сдвиг индексов на 1

b--;

path[a].push_back({b, t}); // В список путей из вершины 'а' добавляем вершину 'b' и длину пути

path[b].push_back({a, t});

}

int start; // Вершина, с которой мы начинаем

cin >> start;

start--; // Сдвигаем индекс

vector<int> count(n, -1); // Счётчик длины путей

count[start] = 0; // Мы находимся в этой вершине, поэтому дистанция до неё равна 0

queue<int> plan; // Наш план посещения вершин. Так как мы используем BFS, то это контейнером является очередь

plan.push(start); // Кладём нашу стартовую вершину в план

while(!plan.empty()) // Наш BFS

{

start = plan.front();

plan.pop();

for(auto next: path[start]) // Достаём наши пары вершина + вес

{

if(count[next[0]] == -1 || count[next[0]] > count[start] + next[1]) // Если вершина не посещена или путь через ту на котором мы сейчас более короткий

{

plan.push(next[0]); // Мы добавляем эту вершину в план

count[next[0]] = count[start] + next[1]; // И отмечаем дистанцию до неё

}

bool delivered = true; // Предпологаем, что мы побывали во всех вершинах, которые нам нужны

int longest = 0; // Положим максимальную дистанцию равной нулю

for(int i = 0; i < m && delivered; i++)

{

if(count[winner[i]] == -1) // Если путь до нужной вершины не был найден

{

delivered = false; // Отмечаем, что мы побывали не везде, где надо

}

longest = max(count[winner[i]], longest);

}

if(delivered) // Если нужные вершины посещены

{

cout << "The good sponsor!\n" << longest; // Выводим фразу и длину пути до самой далёкой вершины

}

else

{

cout << "It is not fault of sponsor...";

}

return 0;

}

Второй вариант

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, m, k;
    cin >> n >> m >> k; // Количество вершин
    vector<int> winner(m);
    for (int i = 0; i < m; i++) // Нужные нам вершины
    {
        cin >> winner[i];
        winner[i]--; // Сдвиг индекса, так как у нас отсчёт в задаче начинается с 1, а в коде с нуля
    }
    vector<vector<int>> path(n, vector<int>(n, 1e6)); // Матрица смежности (1е6 значит, что ребра нет)
    for (int i = 0; i < k; i++)
    {
        int a, b, t;
        cin >> a >> b >> t;
        a--; //Свдиг индекса
        b--;
        if (path[a][b] > t)
        {
            path[a][b] = t;
            path[b][a] = t;
        }
    }
    int start; // Вершина, в которой мы находимся
    cin >> start;
    start--; // Сдвиг индекса
    vector<int> count(n, 1e6); // Счётчик пути до вершин
    vector<bool> used(n, false); // Посещена ли вершина
    count[start] = 0;
    while (start != -1) // Алгоритм Дейкстры
    {
        int next = -1, mini = 1e6;
        for (int j = 0; j < n; j++)
        {
            if (count[j] > count[start] + path[start][j]) // Обновляем расстояние до смежных вершин
            {
                count[j] = count[start] + path[start][j];
            }
            if (count[j] < mini && !used[j]) // Ищем непосещённую вершину с минимальным расстоянием
            {
                next = j;
                mini = count[j];
            }
        }
        used[start] = true; // Отмечаем, что данную вершину мы посетили
        start = next; // Переходим в следующую вершину
    }
    bool deliver = true; // Предположим, что посетили все вершины
    int longest = 0; // Ставим значение, равное минимальному возможному расстоянию
    for (int i = 0; i < m && deliver; i++)
    {
        if (!used[winner[i]]) // Проверяем всем ли победителям доставили призы
        {
            deliver = false;
        }
        longest = max(count[winner[i]], longest); // Ищем максимальную дистанцию
    }
    if (deliver) // Если доставили призы всем
    {
        cout << "The good sponsor!\n" << longest;
    }
    else // Иначе
    {
        cout << "It is not fault of sponsor...";
    }

    return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int main() {

int n, m, k;

cin >> n >> m >> k; // Количество вершин

vector<int> winner(m);

for (int i = 0; i < m; i++) // Нужные нам вершины

{

cin >> winner[i];

winner[i]--; // Сдвиг индекса, так как у нас отсчёт в задаче начинается с 1, а в коде с нуля

}

vector<vector<int>> path(n, vector<int>(n, 1e6)); // Матрица смежности (1е6 значит, что ребра нет)

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

{

int a, b, t;

cin >> a >> b >> t;

a--; //Свдиг индекса

b--;

if (path[a][b] > t)

{

path[a][b] = t;

path[b][a] = t;

}

int start; // Вершина, в которой мы находимся

cin >> start;

start--; // Сдвиг индекса

vector<int> count(n, 1e6); // Счётчик пути до вершин

vector<bool> used(n, false); // Посещена ли вершина

count[start] = 0;

while (start != -1) // Алгоритм Дейкстры

{

int next = -1, mini = 1e6;

for (int j = 0; j < n; j++)

{

if (count[j] > count[start] + path[start][j]) // Обновляем расстояние до смежных вершин

{

count[j] = count[start] + path[start][j];

}

if (count[j] < mini && !used[j]) // Ищем непосещённую вершину с минимальным расстоянием

{

next = j;

mini = count[j];

}

used[start] = true; // Отмечаем, что данную вершину мы посетили

start = next; // Переходим в следующую вершину

}

bool deliver = true; // Предположим, что посетили все вершины

int longest = 0; // Ставим значение, равное минимальному возможному расстоянию

for (int i = 0; i < m && deliver; i++)

{

if (!used[winner[i]]) // Проверяем всем ли победителям доставили призы

{

deliver = false;

}

longest = max(count[winner[i]], longest); // Ищем максимальную дистанцию

}

if (deliver) // Если доставили призы всем

{

cout << "The good sponsor!\n" << longest;

}

else // Иначе

{

cout << "It is not fault of sponsor...";

}

return 0;

}

Объяснение

В данной задаче нам нужно построить граф, где будет $n$ вершин (по количеству участников) и $k$ рёбер (по количеству путей). Граф будет взвешенный и неориентированный. Также у нас будет список $m$ вершин (наши победители) и нам нужно проверить, достижимы ли они из начальной вершины (её номер указывается отдельно в самом конце).

К первому варианту кода

Итак, по входным данным мы строим список смежности и после запускаем поиск в ширину (BFS) из стартовой вершины. Так как граф взвешенный, расстоянием до вершины будем считать совокупный вес рёбер на пути к ней от стартовой вершины. Находясь в какой-либо вершине, мы проверяем, куда мы можем попасть из неё. Если сопряжённая вершина не посещена, то мы добавляем её в план. А если она уже посещена, мы проверяем, будет ли путь через вершину в которой мы находимся, короче того пути, которым мы добирались до этой сопряжённой вершины ранее. Если это так, то мы просто заменяем значение в счётчике пути для сопряжённой вершины и добавляем её в план, ведь если путь до неё стал короче, то и путь «через» неё тоже. После того, как мы нашли наикратчайшие пути до всех достижимых вершин, мы проверяем достигли ли мы всех из списка победителей и находим расстояние до самого дальнего из них. И вывод в зависимости от результата.

Ко второму варианту кода

По входным мы строим матрицу смежности. Для несуществующих рёбер мы ставим значение бесконечность ($10^6$ нам подходит, так как это то значение, которое нам не достичь по ограничениям), а для остальных — их вес. А дальше, из стартовой вершины мы запускаем алгоритм Дейкстры, находя кратчайшие пути до каждой вершины. После идёт проверка, всех ли необходимых вершин мы достигли и расстояние до самой дальней из них. И вывод, в зависимости от результата.

Ссылки

E-olymp (условие).

Ideone (первый вариант кода).

Ideone (второй вариант кода).

Related Images:

e-olymp 2270. Поиск цикла

02/12/2019 by Наташа Писаревская

Задача

Дан ориентированный невзвешенный граф. Необходимо определить есть ли в нём циклы, и если есть, то вывести любой из них.

Входные данные

В первой строке находятся два натуральных числа $n$ и $m$ $($$1$ $\leqslant$ $n$ $\leqslant$ $10$^$5$$, $$1$ $\leqslant$ $m$ $\leqslant$ $10$^$5$$)$ — количество вершин и ребер в графе соответственно. Далее в $m$ строках перечислены рёбра графа. Каждое задаётся парой чисел — номерами начальной и конечной вершин соответственно.

Выходные данные

Если в графе нет цикла, то вывести «NO», иначе вывести «YES» и затем перечислить вершины в порядке обхода цикла.

Тесты

№	Входные данные	Выходные данные
1	2 2 1 2 1 2	NO
2	2 2 1 2 2 1	YES 1 2
3	6 7 1 2 1 5 2 3 2 4 4 6 6 5 5 2	YES 2 4 6 5
4	6 6 1 3 2 4 3 4 1 2 3 5 3 6	NO
5	4 4 1 3 4 2 2 3 3 4	YES 3 4 2

#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> graph; 
vector<int> used, path;
int flag, n, m;
// поиск в глубину для каждой вершины
void dfs (int v) {
    if (flag == 1) return; // если уже нашли цикл, то останавливаемся
    else {
        used[v] = 1; // посещаем вершину 
        path.push_back(v); // добавляем ее в порядок обхода графа
        for (int i = 0; i < graph[v].size(); i++) {
            int to = graph[v][i];// следующая вершина графа
            if (used[to] == 1) { // если мы ее посетили, но не вышли из нее, значит мы нашли цикл
                path.push_back(to); // добавляем следующую вершину в порядок обхода графа
                flag = 1; // ставим индикатор, что мы нашли цикл и останавливаемся
                return;
            } 
            else {
                dfs(to); // если не посетили, то посещаем 
            }
            if (flag == 1) return; // если нашли цикл, то останавливаемся 
        }
        used[v] = 2; // если не нашли цикл, то выходим из вершины 
        path.pop_back();
    }
} 
// проверяем вершины на наличие цикла 
void checkNodes() { 
    for (int i = 1; i <= n; i++) {
        if (used[i] == 0) { // если не посещали вершину, то посещаем ее 
            dfs(i);
            if (flag == 1) return; // если нашли цикл, то останавливаемся
        }   
    }
} 
int main(){
    int v1, v2; 
    cin >> n >> m; // считываем количество вершин и ребер 
    graph.resize(n + 1); 
    used.resize(n + 1, 0);
    for (int i = 0; i < m; i++) {
        cin >> v1 >> v2; // считываем ребра и заполняем граф
        graph[v1].push_back(v2);
    }
    checkNodes();  // проверяем вершины на наличие цикла
    if (flag == 1) { // если цикл найден
        int i = path.size() - 2; // последняя вершина цикла   
        int to = path.back(); // вершина в которой зациклились 
        while (path[i] != to) { // получаем индекс вершины в которой зациклились
            i--;
        }
        cout << "YES" << endl;
        while (i < path.size() - 1) { // выводим сам цикл
            cout << path[i] << " ";
            i++; 
        }
        cout << endl;
    }
    else cout << "NO" << endl;
}

#include <iostream>

#include <vector>

using namespace std;

vector<vector<int>> graph;

vector<int> used, path;

int flag, n, m;

// поиск в глубину для каждой вершины

void dfs (int v) {

if (flag == 1) return; // если уже нашли цикл, то останавливаемся

else {

used[v] = 1; // посещаем вершину

path.push_back(v); // добавляем ее в порядок обхода графа

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

int to = graph[v][i];// следующая вершина графа

if (used[to] == 1) { // если мы ее посетили, но не вышли из нее, значит мы нашли цикл

path.push_back(to); // добавляем следующую вершину в порядок обхода графа

flag = 1; // ставим индикатор, что мы нашли цикл и останавливаемся

return;

}

else {

dfs(to); // если не посетили, то посещаем

}

if (flag == 1) return; // если нашли цикл, то останавливаемся

}

used[v] = 2; // если не нашли цикл, то выходим из вершины

path.pop_back();

}

// проверяем вершины на наличие цикла

void checkNodes() {

for (int i = 1; i <= n; i++) {

if (used[i] == 0) { // если не посещали вершину, то посещаем ее

dfs(i);

if (flag == 1) return; // если нашли цикл, то останавливаемся

}

int main(){

int v1, v2;

cin >> n >> m; // считываем количество вершин и ребер

graph.resize(n + 1);

used.resize(n + 1, 0);

for (int i = 0; i < m; i++) {

cin >> v1 >> v2; // считываем ребра и заполняем граф

graph[v1].push_back(v2);

}

checkNodes(); // проверяем вершины на наличие цикла

if (flag == 1) { // если цикл найден

int i = path.size() - 2; // последняя вершина цикла

int to = path.back(); // вершина в которой зациклились

while (path[i] != to) { // получаем индекс вершины в которой зациклились

i--;

}

cout << "YES" << endl;

while (i < path.size() - 1) { // выводим сам цикл

cout << path[i] << " ";

i++;

}

cout << endl;

}

else cout << "NO" << endl;

}

Решение

Для решения данной задачи воспользуемся поиском в глубину. Также будем отмечать вершины в различными цветами ($0$ (белый) — мы еще не посещали вершину, $1$ (серый) — посетили вершину и не вышли из нее (зациклились), $2$ (черный) — посетили вершину и вышли из неё).

В векторе $graph$ будем хранить сам граф, для проверки на цикличность воспользуемся вектором $visited$, так же будем хранить порядок обхода графа в векторе $path$. Так как по условию, в случае нескольких циклов, необходимо вывести любой, то мы будем находить первый и на этом останавливаться, для этого заведем переменную $flag$, которая равна 1, если цикл уже найден, и равна 0, если цикл еще не найден. В векторе $visited$ будем окрашивать вершину в один из цветов. Если мы захотим посетить $1$ (серую) вершину, то это будет означать, что мы отыскали цикл в этой вершине, тогда устанавливаем $flag = 1$.

Осталось лишь вывести его на экран. Для этого воспользуемся вектором $path$, в котором последний элемент — вершина, в которой цикл. Ищем предпоследнее вхождение этой вершины в векторе $path$ и выводим сам цикл.

Ссылки

Условие задачи на e-olymp

Код программы на ideone

Related Images:

e-olymp 209. Защита от копирования

01/06/2019 by Владислав Бебик

Задача

Давным-давно, в далекой-далекой галактике, когда еще не вышел мультфильм про смешариков, никто не знал про Гарри Поттера и про Властелина Колец, на далекой-далекой планете жили-были полчища смешариков. Их технологии были настолько совершенны, что они создали машину времени и перенеслись на ней в будущее, на планету «Земля», где одному из них совершенно случайно попалась первая серия «Смешариков». Исследователей эта серия так потрясла, что они предприняли чрезвычайно опасный рейд, в ходе которого им удалось добыть полное собрание серий. Эти серии они увезли на родину, где они стали безумно популярными. К сожалению, мультфильмы были с системой защиты от копирования, а смешарики по своей законопослушной сущности не приспособлены к хакерской деятельности. Поэтому им пришлось обмениваться привезенными с Земли дисками.
Местная поп-звезда Билаш обиделся на такую популярность, к которой он не имел никакого отношения, и решил вернуть все в старое русло. Для этого Билаш хочет рассорить смешариков, чтобы они разделились на два не общающихся между собой лагеря. Для того, чтобы поссорить пару смешариков, Билашу требуется израсходовать $1$ у.е. усилий. Но, так как Билаш жутко ленив, он хочет приложить минимум усилий для достижения своей цели. Помогите ему.

Входные данные

На первой строке два числа $N (N ≤ 100)$ и $M$ — количество смешариков и количество пар смешариков, которые обмениваются мультфильмами. На последующих $M$ строках перечисляются пары чисел $U$ и $V$, означающих, что смешарик $U$ и смешарик $V$ знакомы друг с другом и обмениваются мультфильмами.

Выходные данные

Вывести минимальное число у.е., которое придется затратить Билашу на достижение своей цели.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	5 5 1 2 2 3 3 5 5 2 2 4	1
2	12 20 1 2 2 3 3 4 4 5 5 6 6 1 7 8 8 9 9 10 10 11 11 12 12 7 6 3 1 4 2 5 12 9 7 10 8 11 6 12 3 9	2

Код программы

#include <iostream>
#include <vector>
using namespace std;

int n,m;
vector<int> vis;

bool dfs(int w0,int w,vector<vector<int>> &G) {
    vis[w0]=1;
    for (int q=1; q<=n; q++) {
        if (G[w0][q]>0 && vis[q]==0) {
            if (q==w || dfs(q,w,G)==0) {
                G[w0][q]--; 
                G[q][w0]++;
                return 0;
            }
        }
    }
    return 1;
}

int main() {
    int u,v,i,k,res=10000000;
    scanf("%d %d\n",&n,&m);
    vector<vector<int>> G0(n+1,vector<int>(n+1,0));
    for (i=0; i<m; i++) {
        scanf("%d %d\n",&u,&v);
        G0[u][v]=1;
        G0[v][u]=1;
    }
    for (i=2; i<=n; i++) {
        k=0;
        vector<vector<int>> G=G0;
        vis=vector<int>(n+1,0);
        while (!dfs(1,i,G)) {
            k++;
            vis=vector<int>(n+1,0);
        }
        if (k<res) res=k;
    }
    printf("%d",res);
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int n,m;

vector<int> vis;

bool dfs(int w0,int w,vector<vector<int>> &G) {

vis[w0]=1;

for (int q=1; q<=n; q++) {

if (G[w0][q]>0 && vis[q]==0) {

if (q==w || dfs(q,w,G)==0) {

G[w0][q]--;

G[q][w0]++;

return 0;

}

return 1;

}

int main() {

int u,v,i,k,res=10000000;

scanf("%d %d\n",&n,&m);

vector<vector<int>> G0(n+1,vector<int>(n+1,0));

for (i=0; i<m; i++) {

scanf("%d %d\n",&u,&v);

G0[u][v]=1;

G0[v][u]=1;

}

for (i=2; i<=n; i++) {

k=0;

vector<vector<int>> G=G0;

vis=vector<int>(n+1,0);

while (!dfs(1,i,G)) {

k++;

vis=vector<int>(n+1,0);

}

if (k<res) res=k;

}

printf("%d",res);

return 0;

}

Решение задачи

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

Ссылки

Related Images:

e-olymp 4852. Кратчайшее расстояние

23/05/2019 by Владимир Дроздин

Задача взята с сайта e-olymp.

Задача

Дан ориентированный граф. Найдите кратчайшее расстояние от вершины $x$ до всех остальных вершин графа.

Входные данные

В первой строке содержатся два натуральных числа $n$ и $x$ $(1 \leqslant n \leqslant 1000, 1 \leqslant x \leqslant n)$ — количество вершин в графе и стартовая вершина соответственно. Далее в $n$ строках по $n$ чисел — матрица смежности графа: в $i$-ой строке на $j$-ом месте стоит «$1$», если вершины $i$ и $j$ соединены ребром, и «$0$», если ребра между ними нет. На главной диагонали матрицы стоят нули.

Выходные данные

Выведите через пробел числа $d_1$, $d_2$, …, $d_n$, где $d_i$ равно $-1$, если путей между $x$ и $i$ нет, в противном случае это минимальное рaсстояние между $x$ и $i$.

Тесты

#	Входные данные	Выходные данные
1	3 3 0 1 1 1 0 1 1 0 0	1 2 0
2	6 5 0 1 1 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0	2 2 1 1 0 -1
3	3 1 0 0 0 0 0 1 1 1 0	0 -1 -1

Код

#include <iostream>
#include <queue>
using namespace std;
int graph[1001][1001], d[1001];
queue <int> q;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, x, v;
    cin >> n >> x;
    x--;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> graph[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        d[i] = -1;
    }
    q.push(x);
    d[x] = 0;
    while (!q.empty()) {
        v = q.front();
        q.pop();
        for (int i = 0; i < n; i++) {
            if (d[i] == -1 && graph[v][i]) {
                q.push(i);
                d[i] = d[v] + 1;
            }
        }
    } 
    for(int i = 0; i < n; i ++) {
        cout << d[i] << " ";
    }
    return 0;
}

#include <iostream>

#include <queue>

using namespace std;

int graph[1001][1001], d[1001];

queue <int> q;

int main() {

ios_base::sync_with_stdio(false);

cin.tie(NULL);

int n, x, v;

cin >> n >> x;

x--;

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

cin >> graph[i][j];

}

for (int i = 0; i < n; i++) {

d[i] = -1;

}

q.push(x);

d[x] = 0;

while (!q.empty()) {

v = q.front();

q.pop();

for (int i = 0; i < n; i++) {

if (d[i] == -1 && graph[v][i]) {

q.push(i);

d[i] = d[v] + 1;

}

for(int i = 0; i < n; i ++) {

cout << d[i] << " ";

}

return 0;

}

Решение

Данную задачу будем решать поиском в ширину. Сам граф будем хранить в двумерном массиве graph[][], в массиве d[] будем хранить кратчайшее расстояние между заданной вершиной и $i$-ой. В очереди queue <int> q будем хранить обрабатываемые вершины. В самом начале там будет хранится только наша исходная вершина, затем пока в очереди хранятся какие-либо вершины достаем верхнюю и смотрим ребра, выходящие из нее, если ранее вершины не были задействованными, то помещаем в конец очереди. Очередь опустеет, когда будут просмотрены все вершины, в которые можно попасть из исходной $x$. Сложность алгоритма $O(n)$.

Ссылки

ideone

e-olymp

Поиск в ширину на e-maxx

Related Images:

e-olymp 5338. Полный граф — 2

23/05/2019 by Инна Литвиненко

Задача

Обсуждая личную жизнь всевозможных злодеев, мы обделили своим вниманием графа Дуку. Так вот, граф Дуку на досуге любит складывать оригами. Он давно систематизировал свои познания в этой области следующим образом: всего граф знает n фигурок, причем для некоторых из них он знает, как получать из одной другую. Для обучения начинающих ситхов Дуку разработал специальную таблицу. В ячейке $[i, j]$ таблицы стоит «1», если граф может получить из фигурки $i$ фигурку $j$ одним сгибом. Иначе там стоит «0». Изначально в руках у графа Дуку чистый лист, то есть фигурка номер $x$ по его системе, сложить же он желает журавлика – фигурку номер $y$.
Найдите, за сколько операций граф достигнет желаемого.

Входные данные

В первой строке находится число $n (1 \leq n \leq 1000)$. В следующих $n$ строках задана таблица Дуку. В $(n + 1)$ — ой строке стоят числа $x$ и $y$.

Выходные данные

Выведите минимальное количество операций, которые придется осуществить. Если же коварным планам Графа не суждено осуществиться, выведите «-1».

Тесты

№	Ввод	Вывод
1	4 0 0 1 0 0 0 0 1 1 0 0 1 0 1 1 0 1 2	3
2	4 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 1 2	-1
3	5 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 1 5	4
4	2 0 1 1 0 2 1	1
5	6 0 1 1 1 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 5 2	-1

Код

#include <iostream>
#include <queue>
using namespace std;

int main() {
    int n, x, y, v;
    cin >> n;
    int matrix[n + 1][n + 1], dist[n + 1]; 
    queue <int> plan;
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= n; j++)
            cin >> matrix[i][j];
    cin >> x >> y;
    for (int i = 1; i <= n; i++)
        dist[i] = -1;
    plan.push(x);
    dist[x] = 0;
    while (!plan.empty()) {
        v = plan.front();
        plan.pop();
        for (int i = 1; i <= n; i++) {
            if (dist[i] == -1 && matrix[v][i]) {
                plan.push(i);
                dist[i] = dist[v] + 1;
            }
        }
        if (v == y) plan.empty(); // если обработали вершину y, прекращаем обход
    } 
    cout << dist[y];
    return 0;
}

#include <iostream>

#include <queue>

using namespace std;

int main() {

int n, x, y, v;

cin >> n;

int matrix[n + 1][n + 1], dist[n + 1];

queue <int> plan;

for (int i = 1; i <= n; i++)

for (int j = 1; j <= n; j++)

cin >> matrix[i][j];

cin >> x >> y;

for (int i = 1; i <= n; i++)

dist[i] = -1;

plan.push(x);

dist[x] = 0;

while (!plan.empty()) {

v = plan.front();

plan.pop();

for (int i = 1; i <= n; i++) {

if (dist[i] == -1 && matrix[v][i]) {

plan.push(i);

dist[i] = dist[v] + 1;

}

if (v == y) plan.empty(); // если обработали вершину y, прекращаем обход

}

cout << dist[y];

return 0;

}

Решение

Для решения данной задачи достаточно реализовать поиск в ширину на графе. Вершины, которые нужно обработать, будем хранить в очереди, а расстояния от заданной вершины к остальным — в массиве расстояний.

Ссылки

Условие задачи на e-olymp
Код на Ideone
Описание алгоритма на сайте e-maxx.ru

Related Images:

e-olymp 45. Топливо

26/12/2018 by Кирилл Веремйов

Задача

$N$ котелень одинаковой мощности соединены системой трубопроводов из $M$ труб для перекачки топлива. На $09:00$ утра оказалось, что фактические запасы топлива $A_{k}$ тонн $(k=1..N)$ таковы, что в одной из котелень его значительно меньше нормы $B$ тонн, а на остальных — достаточно, либо с избытком.

Суммарные запасы топлива позволяют исправить ситуацию, если перераспределить топливо. В каждый момент времени из $N$ насосов могут работать $0$ или $2$ (в соседних котельных, перекачивающих и принимающих топливо), при этом перекачка одной тонны топлива на $1$ км занимает $C$ минут.

Через какое наименьшее время $T$ минут эта работа будет выполнена?

Входные данные

В первой строке заданы 4 числа $N$,$M$, $B$,$C$. Во второй — массив значений $A_{1..N}$. Далее идут $M$ строк — пары номеров котелень и длины труб между ними. Все данные — неотрицательные целые числа, не превышающие $50$.

Выходные данные

Единственное число — искомое время.

Тесты

5 5 4 6 5 4 8 1 6 1 2 3 2 3 5 2 4 2 3 4 6 3 5 4	102
8 10 8 10 8 11 8 0 8 12 8 12 7 8 2 7 6 4 6 2 3 2 1 4 2 3 1 3 1 2 1 5 9 3 5 6 3 4 5 4 5 2	690
11 10 9 5 9 9 9 9 4 9 12 10 10 9 13 3 1 9 1 2 5 2 8 6 2 7 4 1 4 8 4 5 4 4 6 8 1 9 6 9 10 3 10 11 3	520
2 1 3 1 0 6 1 2 10	30
50 50 43 50 44 44 44 45 2 48 49 46 45 48 43 43 43 45 43 48 49 46 45 48 43 43 43 45 43 48 49 46 45 48 43 44 44 45 43 48 49 46 45 48 44 44 44 45 43 48 49 46 45 48 1 2 1 2 3 1 3 4 1 4 5 1 5 6 1 6 7 1 7 8 1 8 9 1 9 10 1 10 11 1 11 12 1 12 13 1 13 14 1 14 15 1 15 16 1 16 17 1 17 18 1 18 19 1 19 20 1 20 21 1 21 22 1 22 23 1 23 24 1 24 25 1 25 26 1 26 27 1 27 28 1 28 29 1 29 30 1 30 31 1 31 32 1 32 33 1 33 34 1 34 35 1 35 36 1 36 37 1 37 38 1 38 39 1 39 40 1 40 41 1 41 42 1 42 43 1 43 44 1 44 45 1 45 46 1 46 44 1 46 48 1 48 49 1 49 50 1 50 1 1	8400
3 3 1 2 3 0 1 1 3 1 2 3 2 1 2 4	6

Решение 1

#include <iostream>
#include <vector>
using namespace std;
    
int n,m,b,c;

struct boil{
    int mass=0;
    int number=0;
    vector<boil*> address;
    vector<int> distance;
};

int empty=0;
int near_tube=0;
vector<int> visit;

int Min_way(boil* A, int i, int from){
    
    if(A[i].mass>b){
        near_tube=A[i].number;
        return 0;
    }

    int min=0;
    
    bool t=0;
    for(int j=0; j< A[i].distance.size(); j++){
        bool t2=true,t1=true;
        for(int u=0; u<visit.size();u++){
            if(visit[u]==A[i].address[j]->number) t2=false;
            if(visit[u]==A[i].address[min]->number)t1=false;
        }
        if(A[i].address[j]->number==empty || A[i].address[j]->number==from)t2=false;
        if(A[i].address[min]->number==empty ||  A[i].address[min]->number==from)t1=false;
        
        if(A[i].distance[min]>=A[i].distance[j] && t2 || !t1 && t2){
            min=j;
            t=1;
        }
    }
    
    if(t==0){
        if(A[i].distance.size()==1){
            if(A[i].address[0]->mass>b){
                near_tube=A[i].address[0]->number;
                return A[i].distance[0];
            }
            else{
                return -1;
            }
        }
        else return -1;
    }
    else if(A[i].address[min]->mass==b){
        visit.push_back(A[i].number);
        
        bool t1=true;
        long long min2=-1;
        
        for(int k=0; k<visit.size() && t1; k++){
            if(visit[k]==A[i].address[min]->number)t1=false;
        }
        if(A[i].address[min]->number==from)t1=false;
        
        if(t1)  min2=Min_way(A,A[i].address[min]->number,A[i].number);
        if(min2>=0)min2+=A[i].distance[min];
            
        int n1=near_tube;
        
        for(int j=0; j<A[i].distance.size(); j++){
            if(j!=min && A[i].address[j]->mass>=b && A[i].address[j]->number!=from){
                visit.push_back(A[i].number);
                long long a=0;
                bool t3=true;
                for(int k=0; k<visit.size() && t3; k++){
                    if(visit[k]==A[i].address[j]->number)t3=false;
                }
                
                if(A[i].address[j]->number==A[empty].number)t3=false;
                
                
                if(t1 && t3){
                    a=Min_way(A,A[i].address[j]->number,A[i].number);
                }
                else return-1;
                if(a>=0)a+=(A[i].distance[j]);
                
                if(a>=0 && min2>=a && A[near_tube].mass>b ||min2<0){
                    min2=a;
                    n1=near_tube;
                }
                visit.clear();
            }
        }
        near_tube=n1;
        return min2;
    }
    else if(A[i].address[min]->mass<b){
        return -1;
    }
    else{
        near_tube= A[i].address[min]->number;
        return A[i].distance[min];
    }
}

int main() {
    cin>>n>>m>>b>>c;
    boil A[n];
    for(int i=0; i<n; i++){
        int a;
        cin>>a;
        A[i].mass=a;
        A[i].number=i;
        if(A[empty].mass>a)empty=i;
    }
    
    int d,k,g;
    while(cin>>d>>k>>g){
            A[d-1].address.push_back(&A[k-1]);
            A[k-1].address.push_back(&A[d-1]);
            A[k-1].distance.push_back(g);
            A[d-1].distance.push_back(g);
    }

    unsigned long long s=0;
    while(A[empty].mass<b){      
        unsigned long long a=Min_way(A,A[empty].number, A[empty].number);
        if(A[near_tube].mass-b+A[empty].mass<b){
            A[empty].mass+=A[near_tube].mass-b;
            s+=a*(A[near_tube].mass-b);
            A[near_tube].mass=b;
        }
        else{
            int tmp=b-A[empty].mass;
            A[near_tube].mass-=tmp;
            A[empty].mass=b;
            s+=a*tmp;
        }
    }
    
    cout<<s*c;
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

#include <iostream>

#include <vector>

using namespace std;

int n,m,b,c;

struct boil{

int mass=0;

int number=0;

vector<boil*> address;

vector<int> distance;

};

int empty=0;

int near_tube=0;

vector<int> visit;

int Min_way(boil* A, int i, int from){

if(A[i].mass>b){

near_tube=A[i].number;

return 0;

}

int min=0;

bool t=0;

for(int j=0; j< A[i].distance.size(); j++){

bool t2=true,t1=true;

for(int u=0; u<visit.size();u++){

if(visit[u]==A[i].address[j]->number) t2=false;

if(visit[u]==A[i].address[min]->number)t1=false;

}

if(A[i].address[j]->number==empty || A[i].address[j]->number==from)t2=false;

if(A[i].address[min]->number==empty || A[i].address[min]->number==from)t1=false;

if(A[i].distance[min]>=A[i].distance[j] && t2 || !t1 && t2){

min=j;

t=1;

}

if(t==0){

if(A[i].distance.size()==1){

if(A[i].address[0]->mass>b){

near_tube=A[i].address[0]->number;

return A[i].distance[0];

}

else{

return -1;

}

else return -1;

}

else if(A[i].address[min]->mass==b){

visit.push_back(A[i].number);

bool t1=true;

long long min2=-1;

for(int k=0; k<visit.size() && t1; k++){

if(visit[k]==A[i].address[min]->number)t1=false;

}

if(A[i].address[min]->number==from)t1=false;

if(t1) min2=Min_way(A,A[i].address[min]->number,A[i].number);

if(min2>=0)min2+=A[i].distance[min];

int n1=near_tube;

for(int j=0; j<A[i].distance.size(); j++){

if(j!=min && A[i].address[j]->mass>=b && A[i].address[j]->number!=from){

visit.push_back(A[i].number);

long long a=0;

bool t3=true;

for(int k=0; k<visit.size() && t3; k++){

if(visit[k]==A[i].address[j]->number)t3=false;

}

if(A[i].address[j]->number==A[empty].number)t3=false;

if(t1 && t3){

a=Min_way(A,A[i].address[j]->number,A[i].number);

}

else return-1;

if(a>=0)a+=(A[i].distance[j]);

if(a>=0 && min2>=a && A[near_tube].mass>b ||min2<0){

min2=a;

n1=near_tube;

}

visit.clear();

}

near_tube=n1;

return min2;

}

else if(A[i].address[min]->mass<b){

return -1;

}

else{

near_tube= A[i].address[min]->number;

return A[i].distance[min];

}

int main() {

cin>>n>>m>>b>>c;

boil A[n];

for(int i=0; i<n; i++){

int a;

cin>>a;

A[i].mass=a;

A[i].number=i;

if(A[empty].mass>a)empty=i;

}

int d,k,g;

while(cin>>d>>k>>g){

A[d-1].address.push_back(&A[k-1]);

A[k-1].address.push_back(&A[d-1]);

A[k-1].distance.push_back(g);

A[d-1].distance.push_back(g);

}

unsigned long long s=0;

while(A[empty].mass<b){

unsigned long long a=Min_way(A,A[empty].number, A[empty].number);

if(A[near_tube].mass-b+A[empty].mass<b){

A[empty].mass+=A[near_tube].mass-b;

s+=a*(A[near_tube].mass-b);

A[near_tube].mass=b;

}

else{

int tmp=b-A[empty].mass;

A[near_tube].mass-=tmp;

A[empty].mass=b;

s+=a*tmp;

}

cout<<s*c;

return 0;

}

Решение 2

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

struct boil{
    int mass = 0;
    int len = 0;
    char n/*new*/='y';//yes
    char visit = 'n';//no
    vector <int> link;
    vector <int> dis;
};

int main() {
    int N,M,B,C;
    cin >> N >> M >> B >> C;
    boil A[N];
    int need;
    for(int i = 0; i < N ; i++){
        cin >> A[i].mass;
        if(A[i].mass < B)need = i;
    }
    int a, b, s;
    while(cin >> a >> b >> s){
        a--;
        b--;
        A[a].link.push_back(b);
        A[a].dis.push_back(s);
        A[b].link.push_back(a);
        A[b].dis.push_back(s);
    }
    queue <int> A_tmp;
    A_tmp.push(need);
    A[need].n = 'n';
    int ans = 0;
    while(!(A_tmp.empty())){
        int u = A_tmp.front();
        A_tmp.pop();
        A[u].visit = 'y';//yes
            for(int i = 0;i < A[u].link.size(); i++){ 
                if(A[A[u].link[i]].visit == 'n')
                        A_tmp.push(A[u].link[i]);
                if(A[A[u].link[i]].len>A[u].len+A[u].dis[i] || A[A[u].link[i]].n == 'y'){
                    A[A[u].link[i]].len = A[u].len + A[u].dis[i];
                    A[A[u].link[i]].n = 'n';
            }
        }
    }
    while(A[need].mass < B){
        int m = 0;
        for(int i = 0; i < N; i++){
            if((A[i].len < A[m].len || A[m].mass <= B) && i != need && A[i].mass > B)
                m = i;
        }
        if(A[need].mass + (A[m].mass - B) <= B){
            ans += A[m].len * (A[m].mass - B);
            A[need].mass += A[m].mass - B;
            A[m].mass = B;
        }
        else{
            ans += A[m].len * (B - A[need].mass);
            int b = B - A[need].mass;
            A[need].mass = B;
            A[m].mass -= B - A[need].mass;
        }
    }
    cout << ans * C;
    return 0;
}

#include <iostream>

#include <queue>

#include <vector>

using namespace std;

struct boil{

int mass = 0;

int len = 0;

char n/*new*/='y';//yes

char visit = 'n';//no

vector <int> link;

vector <int> dis;

};

int main() {

int N,M,B,C;

cin >> N >> M >> B >> C;

boil A[N];

int need;

for(int i = 0; i < N ; i++){

cin >> A[i].mass;

if(A[i].mass < B)need = i;

}

int a, b, s;

while(cin >> a >> b >> s){

a--;

b--;

A[a].link.push_back(b);

A[a].dis.push_back(s);

A[b].link.push_back(a);

A[b].dis.push_back(s);

}

queue <int> A_tmp;

A_tmp.push(need);

A[need].n = 'n';

int ans = 0;

while(!(A_tmp.empty())){

int u = A_tmp.front();

A_tmp.pop();

A[u].visit = 'y';//yes

for(int i = 0;i < A[u].link.size(); i++){

if(A[A[u].link[i]].visit == 'n')

A_tmp.push(A[u].link[i]);

if(A[A[u].link[i]].len>A[u].len+A[u].dis[i] || A[A[u].link[i]].n == 'y'){

A[A[u].link[i]].len = A[u].len + A[u].dis[i];

A[A[u].link[i]].n = 'n';

}

while(A[need].mass < B){

int m = 0;

for(int i = 0; i < N; i++){

if((A[i].len < A[m].len || A[m].mass <= B) && i != need && A[i].mass > B)

m = i;

}

if(A[need].mass + (A[m].mass - B) <= B){

ans += A[m].len * (A[m].mass - B);

A[need].mass += A[m].mass - B;

A[m].mass = B;

}

else{

ans += A[m].len * (B - A[need].mass);

int b = B - A[need].mass;

A[need].mass = B;

A[m].mass -= B - A[need].mass;

}

cout << ans * C;

return 0;

}

Объяснение 1

Вряд ли было бы понятно, если бы я начал сейчас здесь подробно объяснять код. Поэтому, пояснение именно кода я оставлю по этой ссылке, а тут попробую объяснить идею.

Идея решения сама по себе, думаю, достаточно проста: по сути, простой перебор всех вариантов и нахождение наиболее подходящего. Точнее, как бы строится дерево от котла, где недостаёт топлива, и идёт вычисление расстояния до котла, где есть свободное топливо (по веткам связанных с ним котлов). Несколько более сложная, пожалуй, её реализация. В данном решении я воспользовался рекурсивной функцией, которая возвращает либо расстояние до ближайшего котла, откуда можно взять топливо (общее расстояние- то есть все промежуточные котлы, через которое перекачивается топливо, учитываются), либо возвращает $-1$, что говорит о том, что таких котлов (в данной ветке) нет.

Объяснение 2

И снова, сомневаюсь, что мне тут стоит описывать идею решения. А идея — это алгоритм Дейкстры, и вряд ли я сейчас сделаю объясню его лучше этих сайтов. Поэтому я лучше просто оставлю ссылки на них и на википедию. Отмечу только разницу между переменными $n$ и $visit$ в структуре. $visit$- характеризует вершину, буквально, как посещённую или нет. То есть, рассматривались ли вершины, ведущие из неё. В то время как, $n$— переменная, означающая, принимали ли мы эту вершину во внимание до этого (могли рассматривать путь к данной вершине, но ещё не проверили от неё идущие). Последнюю включил в код просто чтобы не приравнивать $len$ какому-то конкретному числу (по алгоритму, условно, должно быть равно бесконечности). Вектор $dis$-вектор дистанций от данной, к связанной с ней вершинам.

e-olymp

ideone(1)

ideone(2)

Related Images:

e-olymp 4853. Кратчайший путь

26/06/2018 by Андрей Лисовой

Задача

Задан неориентированный граф.
Найдите кратчайший путь от вершины $a$ до вершины $b.$

Входные данные

В первой строке находится два целых числа $n$ и $m$ $(1 \leqslant n \leqslant 50000,$ $1 \leqslant m \leqslant 100000)$ — количества вершин и рёбер соответственно. Во второй строке заданы целые числа $a$ и $b$ — стартовая и конечная вершина соответственно. Далее идут $m$ строк, описывающие рёбра.

Выходные данные

Если пути между $a$ и $b$ нет, то выведите $-1.$ Иначе выведите в первой строке длину $l$ кратчайшего пути между этими двумя вершинами в рёбрах, а во второй строке выведите $l + 1$ число — вершины этого пути.

Тесты

Входные данные	Выходные данные
$4\;5$ $1\;4$ $1\;3$ $3\;2$ $2\;4$ $2\;1$ $2\;3$	$2$ $1\;2\;4$
$5\;4$ $2\;4$ $1\;2$ $2\;3$ $2\;5$ $5\;3$	$-1$
$4\;4$ $2\;3$ $2\;1$ $2\;4$ $4\;3$ $1\;3$	$2$ $2\;1\;3$
$6\;4$ $1\;6$ $1\;2$ $2\;4$ $5\;3$ $4\;5$	$-1$

Код программы

#include <iostream>
#include <vector>
using namespace std;
 
int n,m,a,b,count = 0;
vector<vector<int> > graf; vector<int> ver; vector<int> family; bool ok = false; vector<int> ans; vector<bool> popa;
 
int bfs(int beg, int end){ // функция которая добавляет вершины в вектор вершин,которые мы просмотрим,и помечает их как уже проверенные
    count++;
    if(beg == end){
        ok = true;
        return 1;
    }else{
        for(int i = graf[beg].size() - 1;i >= 0;i--){
            if(!popa[graf[beg][i]]){
                ver.push_back(graf[beg][i]);
                family.push_back(beg);
                popa[graf[beg][i]] = true;
            }
        }
    }
    return 0;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    cin >> a >> b;
    for(int i = 0 ; i <= n; i++){ // создаем векто ввекторов
            graf.push_back(ans);
            popa.push_back(false);
    }
    ver.push_back(a);family.push_back(a);
    for(int i = 0; i < m; i++){ //в вектор вершины добавляем те вершины,с которым она связанна 
        int x,y;
        cin >> x >> y;
        if(x != y){ // проверка на петлю
            graf[x].push_back(y);
            graf[y].push_back(x);
        }
    }
    if(!graf[a].empty()){ //если вершины начала не изолированна 
        while(!ok && count < ver.size() ){ //цикл,пока мы не найдем конечную вершину,или если мы не прошли все вершины в векторе "плана"
            if(bfs(ver[count],b)){ //если мы нашли выход,то начать восстанавливать пути
                count--;// Нам надо начать с последней вершины,а это count - 1 вершина
                int p = 1; //Новая переменная,которая нужна,для нахождения первого вхождения "отца" данной вершины
                ans.push_back(b);//вектор ответа
                while(ver[count] != a){ // пока не дошли до начальной вершины
                    while(ver[p] != family[count]){//двигаемся слева пройденных по вектору вершин плана,и ищем первое вхождение вершины ОТЦА
                        p++;
                    }
                    ans.push_back(ver[p]);//добавляем в ответ вершину,из которой мы попали в предыдущую (отца)
                    count = p;// теперь ищем отца отца и так далее,пока не дойдем до начальной вершины 
                    p = 1;
                }
            }
        }
        if(ans.size() > 0){ // если вектор ответа не пуст(имеет хотябы одну вершины из пути)
            cout << ans.size()-1 << endl;
            for(int i = ans.size()-1; i >= 0; i--){
                cout << ans[i] << " "; // выводим ответ справа на лево,так сказано в условии
            }
        }else{ // иначе -1
            cout << "-1\n";
        }
    }else{//если начальная вершина изолирована,то сразу выводим -1
        cout << "-1\n";
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int n,m,a,b,count = 0;

vector<vector<int> > graf; vector<int> ver; vector<int> family; bool ok = false; vector<int> ans; vector<bool> popa;

int bfs(int beg, int end){ // функция которая добавляет вершины в вектор вершин,которые мы просмотрим,и помечает их как уже проверенные

count++;

if(beg == end){

ok = true;

return 1;

}else{

for(int i = graf[beg].size() - 1;i >= 0;i--){

if(!popa[graf[beg][i]]){

ver.push_back(graf[beg][i]);

family.push_back(beg);

popa[graf[beg][i]] = true;

}

return 0;

}

int main() {

ios::sync_with_stdio(false);

cin >> n >> m;

cin >> a >> b;

for(int i = 0 ; i <= n; i++){ // создаем векто ввекторов

graf.push_back(ans);

popa.push_back(false);

}

ver.push_back(a);family.push_back(a);

for(int i = 0; i < m; i++){ //в вектор вершины добавляем те вершины,с которым она связанна

int x,y;

cin >> x >> y;

if(x != y){ // проверка на петлю

graf[x].push_back(y);

graf[y].push_back(x);

}

if(!graf[a].empty()){ //если вершины начала не изолированна

while(!ok && count < ver.size() ){ //цикл,пока мы не найдем конечную вершину,или если мы не прошли все вершины в векторе "плана"

if(bfs(ver[count],b)){ //если мы нашли выход,то начать восстанавливать пути

count--;// Нам надо начать с последней вершины,а это count - 1 вершина

int p = 1; //Новая переменная,которая нужна,для нахождения первого вхождения "отца" данной вершины

ans.push_back(b);//вектор ответа

while(ver[count] != a){ // пока не дошли до начальной вершины

while(ver[p] != family[count]){//двигаемся слева пройденных по вектору вершин плана,и ищем первое вхождение вершины ОТЦА

p++;

}

ans.push_back(ver[p]);//добавляем в ответ вершину,из которой мы попали в предыдущую (отца)

count = p;// теперь ищем отца отца и так далее,пока не дойдем до начальной вершины

p = 1;

}

if(ans.size() > 0){ // если вектор ответа не пуст(имеет хотябы одну вершины из пути)

cout << ans.size()-1 << endl;

for(int i = ans.size()-1; i >= 0; i--){

cout << ans[i] << " "; // выводим ответ справа на лево,так сказано в условии

}

}else{ // иначе -1

cout << "-1\n";

}

}else{//если начальная вершина изолирована,то сразу выводим -1

cout << "-1\n";

}

return 0;

}

Решение задачи

Раз нам надо найти кратчайший путь, то будем использовать BFS — поиск в ширину. Мы будем постепенно просматривать вершины, внося в «план» те вершины с которыми они связанны и которые еще не внесены в «план». Для удобства используем вектора. В начале создаем вектор векторов, как бы это тавтологически не звучало, для этого я использовал вектор ответа, как объект, который добавлялся в вектор graf, выступающий в роли графа, причем мы добавляем сразу к вершинам graf[x].pushback(y);. То есть $x$-ая вершина получает связь с вершиной $y,$ и наоборот, поскольку граф неориентированный. После чего, проверяем связанна ли начальная вершина хоть с кем-нибудь, если да, то работаем циклом while, пока не наткнемся на начальную вершину, или все вершины в «плане» не будут пройдены. Если мы дошли до конечной вершины, то функция bfs вернет $1,$ что запустит тело if и мы начнем восстанавливать путь. Для этого мы заводили дополнительный вектор family в который по мере добавления в «план», также добавлялись и вершины «отцы»(откуда пришла $i$-ая вершина). Восстановленный путь записываем в вектор ans. После чего while прекращает свою работу и мы переходим к выводу результата. Если вектор ответа пуст, то выводим $-1,$ иначе выводим количество вершин, участвующих в построении пути и сам путь. Задача решена.

Ссылки

Условие задачи на e-olymp
Код решения на ideone.com

Related Images:

e-olymp 4000. Обход в глубину

05/06/2018 by Кирилл Волков

Задача

Дан неориентированный невзвешенный граф, в котором выделена вершина. Вам необходимо найти количество вершин, лежащих с ней в одной компоненте связности (включая саму вершину).

Входные данные

В первой строке содержится количество вершин графа $n$ и выделенная вершина $s$ $\left (1 \leq s \leq n \leq 100 \right).$ В следующих n строках записано по n чисел — матрица смежности графа, в котрой цифра «$0$» означает отсутствие ребра между вершинами, а цифра «$1$» — его наличие. Гарантируется, что на главной диагонали матрицы всегда стоят нули.

Выходные данные

Выведите искомое количество вершин.

Тесты

Входные данные	Выходные данные
3 1 0 0 1 0 0 0 1 0 0	2
4 2 0 1 0 0 1 0 0 1 0 0 0 1 0 1 1 0	4
6 2 0 1 0 0 0 1 1 0 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0	3
4 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0	1
5 3 0 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 1 1 0 1 0	5

Код программы

#include <iostream>
#include <cmath>
#include <iomanip>
#include <vector>

using namespace std;

void dfs(int cur, vector<vector<int>> & adj, vector<bool> & was, int & count){
    if(!was[cur]){
        was[cur] = true;
        count++;
        for(int i = 0; i < adj[cur].size(); i++){
            dfs(adj[cur][i], adj, was, count);
        }
    }
}

int getCount(int start, vector<vector<int>> & adj){
    vector<bool> was(adj.size(), false);
    int count = 0;
    dfs(start, adj, was, count);
    return count;
}

int main() {
    int n;
    cin >> n;
    int start;
    cin >> start;
    start--;
    vector<vector<int>> adj(n, vector<int>());
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            int temp;
            cin >> temp;
            if(temp == 1){
                adj[i].push_back(j);
            }
        }
    }
    cout << getCount(start, adj);
    return 0;
}

#include <iostream>

#include <cmath>

#include <iomanip>

#include <vector>

using namespace std;

void dfs(int cur, vector<vector<int>> & adj, vector<bool> & was, int & count){

if(!was[cur]){

was[cur] = true;

count++;

for(int i = 0; i < adj[cur].size(); i++){

dfs(adj[cur][i], adj, was, count);

}

int getCount(int start, vector<vector<int>> & adj){

vector<bool> was(adj.size(), false);

int count = 0;

dfs(start, adj, was, count);

return count;

}

int main() {

int n;

cin >> n;

int start;

cin >> start;

start--;

vector<vector<int>> adj(n, vector<int>());

for(int i = 0; i < n; i++){

for(int j = 0; j < n; j++){

int temp;

cin >> temp;

if(temp == 1){

adj[i].push_back(j);

}

cout << getCount(start, adj);

return 0;

}

Решение задачи

Для хранения графа воспользуемся списками смежности. Реализуем стандартный поиск в глубину. Пусть $c$ количество вершин в компоненте графа. Изначально $c = 0.$ При посещении очередной, не посещенной ранее вершины, значение $c$ увеличивается на один. Таким образом, при полном обходе компоненты графа $c$ будет искомым числом.

Ссылки

Условие задачи на e-olymp
Решение на e-olymp
Код решения на Ideone

Related Images:

e-olymp 209. Защита от копирования

29/05/2018 by Александра Рябова

Условие

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

Входные данные

На первой строке два числа $N$ $(N \le 100)$ и $M$ — количество смешариков и количество пар смешариков, которые обмениваются мультфильмами. На последующих $M$ строках перечисляются пары чисел $U$ и $V$, означающих, что смешарик $U$ и смешарик $V$ знакомы друг с другом и обмениваются мультфильмами.

Выходные данные

Вывести минимальное число у.е., которое придется затратить Билашу на достижение своей цели.

Тесты

Ввод	Вывод
$5$ $5$ $1$ $2$ $3$ $2$ $2$ $4$ $3$ $5$ $2$ $5$	$1$
$5$ $5$ $1$ $3$ $3$ $5$ $5$ $2$ $2$ $4$ $4$ $1$	$2$
$2$ $1$ $2$ $1$	$1$

Код

#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 500;
int g[MAXN][MAXN];
int best_cost = 1000000000;
 
void mincut(int n) {
    vector< int> v[MAXN];
    for (int i = 0; i < n; ++i) v[i].assign (1, i);
    int w[MAXN];
    bool exist [MAXN], in_a [MAXN];
    for (auto &e :exist) e = true;
    for (int ph = 0; ph < n-1; ++ph) {
        for (auto &e: in_a) e = false;
        for (auto &e: w) e = 0;
        for (int it = 0, prev; it< n-ph; ++it) {
            int sel = -1;
            for (int i = 0; i < n; ++i)
                if (exist[i] && !in_a[i] && (sel == -1 || w[i] > w[sel])) sel = i;
            if (it == n-ph-1) {
                if (w[sel] < best_cost)
                    best_cost = w[sel];
                v[prev].insert (v[prev].end(), v[sel].begin(), v[sel].end());
                for (int i=0; i<n; ++i)
                    g[prev][i] = g[i][prev] += g[sel][i];
                exist[sel] = false;
            }
            else {
                in_a[sel] = true;
                for (int i = 0; i < n; ++i) w[i] += g[sel][i];
                prev = sel;
            }
        }
    }
}
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++){
        int a,b;
        cin >> a >> b;
        a--;
        b--;
        g[a][b] = 1;
        g[b][a] = 1;
    }
    mincut (n);
    cout << best_cost;
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

const int MAXN = 500;

int g[MAXN][MAXN];

int best_cost = 1000000000;

void mincut(int n) {

vector< int> v[MAXN];

for (int i = 0; i < n; ++i) v[i].assign (1, i);

int w[MAXN];

bool exist [MAXN], in_a [MAXN];

for (auto &e :exist) e = true;

for (int ph = 0; ph < n-1; ++ph) {

for (auto &e: in_a) e = false;

for (auto &e: w) e = 0;

for (int it = 0, prev; it< n-ph; ++it) {

int sel = -1;

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

if (exist[i] && !in_a[i] && (sel == -1 || w[i] > w[sel])) sel = i;

if (it == n-ph-1) {

if (w[sel] < best_cost)

best_cost = w[sel];

v[prev].insert (v[prev].end(), v[sel].begin(), v[sel].end());

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

g[prev][i] = g[i][prev] += g[sel][i];

exist[sel] = false;

}

else {

in_a[sel] = true;

for (int i = 0; i < n; ++i) w[i] += g[sel][i];

prev = sel;

}

int main() {

int n, m;

cin >> n >> m;

for (int i = 0; i < m; i++){

int a,b;

cin >> a >> b;

a--;

b--;

g[a][b] = 1;

g[b][a] = 1;

}

mincut (n);

cout << best_cost;

return 0;

}

Решение

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

Ссылки

Условие на e-olymp.com
Код на ideone.com

Related Images:

e-olymp 610. Древняя рукопись

19/05/2018 by Мороз Дима

Задача

В некоторой древней стране жили-были братья. Сколько их было, нам точно не известно, но в исторических источниках упоминается, что их точно было не менее трех. С течением времени у них появились дети и разбрелись они по миру, причем как и их родители, каждый построил свой город. Опять же с течением времени количество родственников начало стремительно возрастать и решили они между некоторыми городами построить дороги, а некоторые из них, уже до этого успели построить и объездные дороги вокруг своего города. В рукописях упоминается, что количество городов в той стране не превышало $8000$. Кроме того, в тех же рукописях содержались схематические карты, которые показывали наличие дорог между городами, или объездной дороги вокруг города. Карты имели вид квадратных матриц, в которых цифра $1$ указывала на наличие дороги между городами, или вокруг города, или $0$ в случае отсутствия таковой.

Изучите древние рукописи и дайте ответ на вопрос: а сколько же дорог было построено между городами?

Входные данные

В первой строке задано количество городов $n$, а в последующих $n$ строках через пробел задано по $n$ чисел, которые указывают на наличие или отсутствие соответствующей дороги.

Выходные данные

Количество построенных между городами дорог.

Тесты

Входные данные	Выходные данные
5 1 1 1 1 0 1 0 1 0 1 1 1 1 0 1 1 0 0 0 1 0 1 1 1 1	7
4 0 1 0 1 1 1 0 1 0 0 1 0 1 1 0 0	3
3 1 1 0 1 0 1 0 1 0	2
3 0 1 1 1 0 1 1 1 0	3
3 1 0 0 0 1 0 0 0 1	0

Код программы

#include <iostream>
#include <stdio.h>
using namespace std;

int main() {
    int n, k = 0;
    cin >> n;     cin.ignore(); //считываем n и игнорируем символ перевода строки
    const int N = 2 * n + 1;
    char c[N];
    for(int i = 0; i < n; i++) {
        fgets(c, N, stdin); //считываем строку
        for(int j = 0; j < i; j++) 
            k = k + c[j << 1] - 48; //переводим символ из ascii кода в число
    }
    cout << k;

    return 0;
}

#include <iostream>

#include <stdio.h>

using namespace std;

int main() {

int n, k = 0;

cin >> n; cin.ignore(); //считываем n и игнорируем символ перевода строки

const int N = 2 * n + 1;

char c[N];

for(int i = 0; i < n; i++) {

fgets(c, N, stdin); //считываем строку

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

k = k + c[j << 1] - 48; //переводим символ из ascii кода в число

}

cout << k;

return 0;

}

Решение задачи

Задача не сложная – посчитать количество ребер в графе, заданном матрицей смежности.

Сложность задачи состоит в ограничениях по времени – не более одной секунды (ощутимо при больших значенях $n$, так как $3 ≤ n ≤ 8000$). Поэтому приходится быстро вводить данные в больших количествах. Для этого используем символьный массив и любую функцию, которая читает целую строку чисел (в моем случае – fgets()), которая читает строку, пока не встретит символ перевода строки – '\n'.

Далее по одному переводим символы в числа и суммируем их в переменной k, после чего выводим.

Ссылки

Условие задачи на e-olymp.com
Решение задачи на ideone.com

Related Images:

e-olymp 93. Truck driving

12/04/2018 by Александра Рябова

Task

Umidsh Izadish is a truck driver and wants to drive from a city to another city while there exists a dedicated straight road between each pair of cities in that country. Amount of consumed fuel is the distance between two cities which is computed from their coordinates. There is a gas station in each city, so Umidsh can refuel the gas container of his truck. Your job is to compute the minimum necessary volume of gas container of Umidsh’s Truck.

Input data

The first line of input contains an integer, the number of test cases. Following, there are data for test cases. Each test case begins with a line containing one integer, $C$ $(2 ≤ C ≤ 200)$, which is the number of cities. The next $C$ lines each contain two integers $x$, $y$ $(0 ≤ x, y≤ 1000)$ representing the coordinate of one city. First city is the source city and second is the destination city of Umidsh.

Output data

There should be one line for each test case in output. Each line should contain one floating point number which is the minimum necessary volume of truck’s gas container, printed to three decimals.

Tests

Input	Output
$2$ $2$ $0$ $0$ $3$ $4$ $3$ $17$ $4$ $19$ $4$ $18$ $5$	$5.000$ $1.414$
$1$ $3$ $4$ $5$ $4$ $6$ $4$ $7$	$1.000$
$2$ $4$ $0$ $1$ $0$ $-1$ $1$ $0$ $-1$ $0$ $3$ $8$ $9$ $0$ $1$ $14$ $14$	$1.414$ $11.314$
$3$ $2$ $1$ $1$ $1$ $2$ $5$ $8$ $6$ $3$ $3$ $4$ $1$ $7$ $7$ $5$ $0$ $3$ $1$ $1$ $1$ $3$ $2$ $5$	$1.000$ $5.657$ $2.000$

Code

#include <iostream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

const int inf = 10000000;

struct node {
    int x;
    int y;
};

vector <node> cities;
int d [200];
void diikstra ( int n ){
    d[0] = 0;
    for (int i = 1; i < n; i++){
        d[i] = inf;
    }
    priority_queue < pair <int, int> > q;
    q.push({d[0], 0});
    while (!q.empty()) {
        int num_v = q.top().second;
        node cur = cities[num_v];
        int distv = -q.top().first;
        q.pop();
        for (int i = 0; i < n; i++) {
             int distance = max (distv, (cur.x - cities[i].x)*(cur.x - cities[i].x)+(cur.y - cities[i].y)*(cur.y - cities[i].y));
                     if(d[i] > distance){
                        d[i] = distance;
                        q.push ({-distance, i});
                    }
        }
            }
}
int main() {
    cout.precision(3);
    int q;
    cin >> q;
    for (int w = 0; w < q; w++){
        int n;
        cin >> n;
        for (int i = 0; i < n; i++){
            int a, b;
            cin >> a >> b;
            cities.push_back({a,b});
        }
        diikstra (n);
        for (int i = 0; i < n; i++){
            cities.pop_back();
        }
        cout << fixed << sqrt(d[1]) <<  endl;
        
        
    }
    return 0;
}

#include <iostream>

#include <iomanip>

#include <cmath>

#include <algorithm>

#include <vector>

#include <queue>

using namespace std;

const int inf = 10000000;

struct node {

int x;

int y;

};

vector <node> cities;

int d [200];

void diikstra ( int n ){

d[0] = 0;

for (int i = 1; i < n; i++){

d[i] = inf;

}

priority_queue < pair <int, int> > q;

q.push({d[0], 0});

while (!q.empty()) {

int num_v = q.top().second;

node cur = cities[num_v];

int distv = -q.top().first;

q.pop();

for (int i = 0; i < n; i++) {

int distance = max (distv, (cur.x - cities[i].x)*(cur.x - cities[i].x)+(cur.y - cities[i].y)*(cur.y - cities[i].y));

if(d[i] > distance){

d[i] = distance;

q.push ({-distance, i});

}

int main() {

cout.precision(3);

int q;

cin >> q;

for (int w = 0; w < q; w++){

int n;

cin >> n;

for (int i = 0; i < n; i++){

int a, b;

cin >> a >> b;

Задача

Входные данные

Выходные данные

Тесты

Код программы

Решение задачи

Алгоритм

Оптимизация

Ссылки

Related Images:

Problem

Input

Output

Tests

Code

Solution

Links&References

Related Images:

Условие

Входные данные

Выходные данные

Тесты

Код

Решение

Ссылки

Related Images:

Задача

Входные данные:

Выходные данные:

Тесты

Код

Решение

Ссылки

Related Images:

Условие задачи

Входные данные

Выходные данные

Тесты

Код

Решение задачи

Первый этап

Второй этап

Описание алгоритма

Подготовка

Первый этап

Второй этап

Related Images:

Задача

Входные данные

Выходные данные

Тесты

Код программы

Объяснение

Ссылки

Related Images:

Задача

Входные данные

Выходные данные

Тесты

Код программы

Первый вариант

Второй вариант

Объяснение

К первому варианту кода

Ко второму варианту кода

Ссылки

Related Images:

Задача

Входные данные

Выходные данные

Тесты

№

Входные данные

Выходные данные

Решение

Ссылки

Related Images:

Задача

Входные данные

Выходные данные