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 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 8651. Браслети (Bangles)

14/06/2019 by Руслан Масальский

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

Шпигунам-конкурентам вдалося потрапити на склад запасних частин фірми «Magic & Stupidity», яка виготовляла магічні браслети. Стало зрозуміло, що всі браслети складалися з чотирьох різних деталей, кожна з яких мала на кінцях замки різних типів (розрізнялися за номерами). Вони з’єднувалися по колу, причому у сусідніх частин замки повинні мати однаковий номер. Знайшлося $N$ різних типів замків (позначимо їх номерами від $1$ до $N$) і $М$ типів деталей, які визначаються парою номерів замків (порядок несуттєвий). Напишіть програму, яка б підраховувала скільки існує різних наборів з чотирьох деталей для виготовлення браслетів фірмою «Magic & Stupidity».

Вхідні дані

Програма читає з першого рядка числа $N$ (кількість типів замків) та $M$ (кількість типів деталей). ($4 \leqslant N \leqslant 300$). У $M$ наступних рядках наведені параметри деталей (пара номерів замків). Всі пари різні.

Вихідні дані

Програма визначає кількість варіантів браслетів.

Тести

№	Inputs	Outputs
1	5 7 1 3 1 4 2 4 2 5 3 4 3 5 4 5	2
2	4 4 1 2 2 3 3 4 1 4	1
3	5 5 1 2 2 3 3 5 1 4 1 5	1

Код

#include <iostream>
using namespace std;
typedef long long ll;
const ll INF = 3e2+5;
ll arr[INF][INF];
void power(ll n){
    ll arr1[n][n];
    for(int i  = 0 ; i < n ; i++){
        for(int j = 0 ; j < n; j++){
            arr1[i][j]=0;
            for(int k = 0 ; k < n ; k ++){
                arr1[i][j]+=arr[i][k]* arr[k][j];
            }
            
        }
    }
    for(int i  = 0 ; i < n ; i++){
        for(int j = 0 ; j < n; j++){
            arr[i][j]=arr1[i][j];
        }
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,m ;
    cin>>n>>m;
    ll a,b;
    for(int i = 0 ; i < m ; i++){
        cin>>a>>b;
        a--;
        b--;
        if(a!=b){
            arr[a][b]++;
            arr[b][a]++;    
        }
    }
    power(n);
    ll to_del[n];
    for(int i = 0 ; i < n; i++){
        to_del[i]=0;
        for(int j = 0 ; j < n; j++){
            if(i==j){
                arr[i][i] = 0;
            }else{
                to_del[i]+=arr[i][j];
            }
        }
    }
    power(n);
    ll answer =0;
    for(int i = 0 ; i < n ; i++){
        answer +=arr[i][i]-to_del[i];
    }
    cout<<answer/8;
    return 0;
}

#include <iostream>

using namespace std;

typedef long long ll;

const ll INF = 3e2+5;

ll arr[INF][INF];

void power(ll n){

ll arr1[n][n];

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

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

arr1[i][j]=0;

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

arr1[i][j]+=arr[i][k]* arr[k][j];

}

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

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

arr[i][j]=arr1[i][j];

}

int main() {

ios_base::sync_with_stdio(0);

cin.tie(0);

int n,m ;

cin>>n>>m;

ll a,b;

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

cin>>a>>b;

a--;

b--;

if(a!=b){

arr[a][b]++;

arr[b][a]++;

}

power(n);

ll to_del[n];

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

to_del[i]=0;

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

if(i==j){

arr[i][i] = 0;

}else{

to_del[i]+=arr[i][j];

}

power(n);

ll answer =0;

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

answer +=arr[i][i]-to_del[i];

}

cout<<answer/8;

return 0;

}

Рішення

Зробимо ізоморфний перехід в графи, а саме можна помітити, що визначивши типи запків як вершини матимемо зв’язки між типами, як існуючий елемент браслета, тобто пара $(1, 2)$ насправді задає зв’язок між першим і другим типом. Маэмо граф, залишилось знайти кількість простих циклів завдовшки у чотири ребра (чотири вершини).
Построївши матрицю суміжності ми на справді побудували матрицю де arr[i][j] містить кількість способів дійти від вершини $i$ до вершини $j$ за один хід.
Нехай за х ходів ми потрапили з вершини $i$ у вершину $k$ рівно $a$ способами, а з вершини $k$ у вершину $j$ рівно $b$ способами. Тоді за $2x$ ходів ми можемо потрапити з вершини $i$ у вершину $j$ через вершину $k$ рівно $ab$ способами, що насправді еквівалентно возведенню матриці суміжності у степінь, яка дорівнює кількості ходів
Тепер за два перемноження отримаємо матрицю де arr[i][j] містить кількість способів дійти від вершини $i$ до вершини $j$ за 4 ходи. Сумма елементів на головній діагоналі майже дає нам потрібний результат. Нам треба відняти ходи такого типу 1-2-1-2-1 та 1-2-3-2-1. Щоб відняти ходи першого типу після першого перемноження поставимо на головній діагоналі нулі, що означатиме що ми не можемо у другому ході повернутися у ту вершину з якої прибули. Для другого типу треба помітити, що ми йдемо по тому шляху, по якому вже йшли тобто якщо мі за два ходи дійшли до певної вершини $a$ способами, то повертаючись назад отримаємо $2a$ способів, але з них рівно $a$ нам не підходять, тому після другого перемноження с діагоналі видаляємо сумму на ряді на моменті коли було зроблено усього $2$ ходи, звісно не враховуючи елементи на головній діагоналі. Ми будували неорієнтований граф тому сумму на діагоналі треба поділити на $2,$ а ще в наших циклах по $4$ вершини, тому треба ще поділити на 4.

Посилання

ideone
e-olymp

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 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 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;

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;

}

Solution

We can interpretate the set of the cities as weighted graph, which vertices represent cities and weight of each edge between two vertices is the gas volume required for passing the distance between corresponding cities.
The volume of truck’s gas container depends on the gas volume required for arrival to the each next station of the Umidsh’s way. The maximum between gas volume required to get to the city $A$ and gas volume required to pass the way from the city $A$ to the city $B$ represents the minimum necessary gas volume required to get to the city $B$ through the city $A$. So the volume of truck’s gas container would turn to minimum, when the maximum gas volume required for passing the distance between each two stations of his way would turn to minimum. Thus we could use modified Dijkstra’s algorithm to find the biggest value among the weights of an edges between each two stations of the way between vertice 0 and vertice 1.

References

The task at E-Olymp
My solution at ideone

Related Images:

A1038. Дейкстра?

06/12/2017 by Калачьов Андрій Сергійович

Задача: Имеется [latex]n [/latex] городов. Некоторые из них соединены дорогами известной длины. Вся система дорог задана квадратной матрицей порядка [latex]n [/latex], элемент [latex]a_{ij} [/latex] которой равен некоторому отрицательному числу, если город [latex]i [/latex] не соединен напрямую дорогой с городом [latex]j [/latex] и равен длине дороги в противном случае latex [/latex].

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

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

-1	2	4	-1
2	-1	1	6
4	1	-1	1
-1	6	1	-1

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

1 > 2 = 2

1 > 3 = 3

1 > 4 = 4

Длина кратчайшей цепи, проходящей через все вершины 4

Ссылка на ideone: http://ideone.com/iXjoLZ

Решение:

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

int main(){
    int n,st=0,sum=0; 
    bool p=true;
    cin>>n;
    int GR[n][n]; 
    int distance[n];
    bool visited[n];    
    int index;
    for (int i=0; i<n; i++){
        distance[i]=INT_MAX; visited[i]=false; 
        for (int j=0; j<n; j++){
            cin>>GR[i][j];
            if (GR[i][j]<0 && i!=j)p=false;
        }
    }    
    if (p==true){
        for (int i=0; i<n-1; i++){
            int minl=INT_MAX;
            for (int j=0; j<n; j++){
                if (GR[i][j]<minl && GR[i][j]>0 && j>i) minl=GR[i][j];
            }
            sum+=minl;
        }
    }    
    distance[st]=0;
    for (int p=0; p<n-1; p++){
        int min=INT_MAX;
        for (int i=0; i<n; i++){
            if (!visited[i] && distance[i]<min){
                min=distance[i]; index=i;
            }
        }    
        visited[index]=true;
        for (int i=0; i<n; i++){
            if (!visited[i] && GR[index][i]>0 && distance[index]!=INT_MAX && distance[index]+GR[index][i]<distance[i]){
                distance[i]=distance[index]+GR[index][i]; 
            }
        }    
    }
    for (int i=1; i<n; i++){
        if (distance[i]!=INT_MAX) cout<<st+1<<" > "<<i+1<<" = "<<distance[i]<<endl;
        else cout<<st+1<<" > "<<i+1<<" = "<<"Маршрут недоступен"<<endl;
    }    
    if (p==true) cout<<"Длина кратчайшей цепи, проходящей через все вершины "<<sum;
    else cout<<"Не все вершины графа соединены";
}

#include <iostream>

#include <climits>

using namespace std;

int main(){

int n,st=0,sum=0;

bool p=true;

cin>>n;

int GR[n][n];

int distance[n];

bool visited[n];

int index;

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

distance[i]=INT_MAX; visited[i]=false;

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

cin>>GR[i][j];

if (GR[i][j]<0 && i!=j)p=false;

}

if (p==true){

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

int minl=INT_MAX;

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

if (GR[i][j]<minl && GR[i][j]>0 && j>i) minl=GR[i][j];

}

sum+=minl;

}

distance[st]=0;

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

int min=INT_MAX;

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

if (!visited[i] && distance[i]<min){

min=distance[i]; index=i;

}

visited[index]=true;

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

if (!visited[i] && GR[index][i]>0 && distance[index]!=INT_MAX && distance[index]+GR[index][i]<distance[i]){

distance[i]=distance[index]+GR[index][i];

}

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

if (distance[i]!=INT_MAX) cout<<st+1<<" > "<<i+1<<" = "<<distance[i]<<endl;

else cout<<st+1<<" > "<<i+1<<" = "<<"Маршрут недоступен"<<endl;

}

if (p==true) cout<<"Длина кратчайшей цепи, проходящей через все вершины "<<sum;

else cout<<"Не все вершины графа соединены";

}

Алгоритм: Для решения задачи применим алгоритм Дейкстры. Применяя этот алгоритм мы считаем что у нас нету ребер с отрицательным весом. Если вес ребра отрицательный, то его просто не существует (по условию задачи). Вводим матрицу смежности графа и проверяем является ли граф полным (для задания 2). Если граф является полным, то ищем для каждой вершины инцидентное ребро с минимальным весом и суммируем (задание 2). В цикле каждой вершине присваиваем минимально расстояние до нее от первой вершины и записываем в массив (задание 1).

Related Images:

e-olymp 1947. Конденсация графа

25/05/2017 by Валентина Андриеш

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

Для заданного ориентированного графа найти количество ребер в его конденсации.

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

Конденсация графа не содержит кратных ребер.

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

Первая строка содержит два натуральных числа n и m (n ≤ 10000, m ≤ 100000) — количество вершин и ребер графа соответственно. Каждая из следующих m строк содержит описание ребра графа. Ребро номер i описывается двумя натуральными числами [latex]b_{i}[/latex], [latex]e_{i}[/latex](1 ≤ [latex]b_{i}[/latex], [latex]e_{i}[/latex] ≤ n) — номерами начальной и конечной вершины соответственно. В графе могут присутствовать кратные ребра и петли.

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

Количество ребер в конденсации графа.

Тесты:

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

#include <iostream>
#include <vector>
#include <set>

using namespace std;

struct vertex{          
    int used,colour;
    vector<int>graph,graph_transposed;
};

void dfs_g(int v, vector<vertex>&components, vector<int>&list){
    components[v].used = 1;
    for (int i = 0; i < components[v].graph.size(); i++){
        if(components[components[v].graph[i]].used!=1) dfs_g(components[v].graph[i],components,list);
    }
    list.push_back(v);
}

void dfs_tg(int v, int color, vector<vertex>&components){
    components[v].used=2;
    components[v].colour=color;
    for (int i=0; i<components[v].graph_transposed.size(); i++){
        if (components[components[v].graph_transposed[i]].used != 2)dfs_tg(components[v].graph_transposed[i],color,components);
    }
}

int main(){
    int n,m,color=0,answer=0;
    cin>>n>>m;
    vector<int>list(n);
    vector<vertex>components(n);
    set<int>ribs[10000];
    for(int i=0; i<m; i++){
        int a,b;
        cin>>a>>b;
        components[a-1].graph.push_back(b-1);
        components[b-1].graph_transposed.push_back(a-1);
    }

    for (int i=0; i<n; i++){
        if (components[i].used!=1)dfs_g(i,components,list);
    }
    for (int i=list.size()-1; i>=0; i--){
        if (components[list[i]].used != 2){
            dfs_tg(list[i], color, components);
            color++;
        }
    }
    for(int i=0; i<n; i++){
        for(int j=0; j<components[i].graph.size(); j++){
            if(components[i].colour!=components[components[i].graph[j]].colour){
                ribs[components[i].colour].insert(components[components[i].graph[j]].colour);
            }
        }
    }
    for(int i=0; i<10000; i++)answer+=ribs[i].size();
    cout<<answer;
    return 0;
}

#include <iostream>

#include <vector>

#include <set>

using namespace std;

struct vertex{

int used,colour;

vector<int>graph,graph_transposed;

};

void dfs_g(int v, vector<vertex>&components, vector<int>&list){

components[v].used = 1;

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

if(components[components[v].graph[i]].used!=1) dfs_g(components[v].graph[i],components,list);

}

list.push_back(v);

}

void dfs_tg(int v, int color, vector<vertex>&components){

components[v].used=2;

components[v].colour=color;

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

if (components[components[v].graph_transposed[i]].used != 2)dfs_tg(components[v].graph_transposed[i],color,components);

}

int main(){

int n,m,color=0,answer=0;

cin>>n>>m;

vector<int>list(n);

vector<vertex>components(n);

set<int>ribs[10000];

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

int a,b;

cin>>a>>b;

components[a-1].graph.push_back(b-1);

components[b-1].graph_transposed.push_back(a-1);

}

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

if (components[i].used!=1)dfs_g(i,components,list);

}

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

if (components[list[i]].used != 2){

dfs_tg(list[i], color, components);

color++;

}

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

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

if(components[i].colour!=components[components[i].graph[j]].colour){

ribs[components[i].colour].insert(components[components[i].graph[j]].colour);

}

for(int i=0; i<10000; i++)answer+=ribs[i].size();

cout<<answer;

return 0;

}

Описание решения задачи:

Компонентой сильной связности называется такое подмножество вершин C, что любые две вершины этого подмножества достижимы друг из друга. Отсюда следует, что конденсация это граф, получаемый из исходного графа сжатием каждой компоненты сильной связности в одну вершину. Отсюда имеем структуру [latex]vertex[/latex]. Основным фундаментом данного алгоритма является следующая теорема: Пусть [latex]C[/latex] и [latex]{C}'[/latex] — две различные компоненты сильной связности, и пусть в графе конденсации между ними есть ребро ([latex]C[/latex],[latex]C'[/latex]). Тогда время выхода из [latex]C[/latex] будет больше, чем время выхода из [latex]{C}'[/latex]. Базируясь на этом, выполним серию обходов в глубину с помощью функции [latex]dfs[/latex] _ [latex]g[/latex], посещая весь граф. С визитом всех вершин графа,запоминаем для каждой время выхода, записывая это в созданный [latex]list[/latex]. Далее строится транспонированный граф. Запускаем серию обходов в глубину(функция [latex]dfs[/latex] _ [latex]tg[/latex]) этого графа в порядке, определяемом списком [latex]list[/latex] (а именно, в обратном порядке, т.е. в порядке уменьшения времени выхода). Каждое множество вершин, достигнутое в результате рекурсивного запуска обхода, и будет очередной компонентой сильной связности. Окрасим все вершины каждой сильной компоненты связности в один уникальный цвет, для этого зададим в структуре параметр [latex]colour[/latex]. Число цветов окраски будет равно количеству компонент сильной связности. Далее перебираем все ребра исходного графа. Если ребро соединяет вершины разного цвета, то оно принадлежит конденсации графа. Для каждого ребра ([latex]a[/latex], [latex]b[/latex]), для которого [latex]components[a].colour[/latex] [latex]≠[/latex] [latex]components[b].colour[/latex], занесем во множество [latex]ribs[/latex] данную пару. Количество элементов во множестве [latex]ribs[/latex] будет равняться числу ребер в конденсации графа.

Условие задачи
Код задачи на с++
Засчитанное решение на e-olymp

Related Images:

Код Хаффмана

15/04/2017 by Вадим Гордийчук

Задача

Дана строка, после которой следует символ перехода на следующую строку (далее — endl. Вывести:

Код графа на языке DOT, иллюстрирующий кодирование символов строки;
Символы строки и соответствующие им коды Хаффмана;
Закодированную строку.

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

Некоторая последовательность символов и endl.

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

Код графа на языке DOT, иллюстрирующий кодирование символов строки;
Символы строки и соответствующие им коды Хаффмана;
Закодированная строка.

Тест

Входные данные	Выходные данные
MOLOKO KIPIT	digraph G { "'MLO KITP', 12, code: ''" -> "'MLO', 5, code: '0'" [ label = "0" ]; "'MLO KITP', 12, code: ''" -> "' KITP', 7, code: '1'" [ label = "1" ]; "'MLO', 5, code: '0'" -> "'ML', 2, code: '00'" [ label = "0" ]; "'MLO', 5, code: '0'" -> "'O', 3, code: '01'" [ label = "1" ]; "'ML', 2, code: '00'" -> "'M', 1, code: '000'" [ label = "0" ]; "'ML', 2, code: '00'" -> "'L', 1, code: '001'" [ label = "1" ]; "' KITP', 7, code: '1'" -> "' K', 3, code: '10'" [ label = "0" ]; "' KITP', 7, code: '1'" -> "'ITP', 4, code: '11'" [ label = "1" ]; "' K', 3, code: '10'" -> "' ', 1, code: '100'" [ label = "0" ]; "' K', 3, code: '10'" -> "'K', 2, code: '101'" [ label = "1" ]; "'ITP', 4, code: '11'" -> "'I', 2, code: '110'" [ label = "0" ]; "'ITP', 4, code: '11'" -> "'TP', 2, code: '111'" [ label = "1" ]; "'TP', 2, code: '111'" -> "'T', 1, code: '1110'" [ label = "0" ]; "'TP', 2, code: '111'" -> "'P', 1, code: '1111'" [ label = "1" ]; } Codes of letters: 'O'(01) 'K'(101) 'I'(110) 'T'(1110) 'P'(1111) 'M'(000) 'L'(001) ' '(100) Encoded string: 00001001011010110010111011111101110

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

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

MOLOKO KIPIT

digraph G {
"'MLO KITP', 12, code: ''" -> "'MLO', 5, code: '0'" [ label = "0" ];
"'MLO KITP', 12, code: ''" -> "' KITP', 7, code: '1'" [ label = "1" ];
"'MLO', 5, code: '0'" -> "'ML', 2, code: '00'" [ label = "0" ];
"'MLO', 5, code: '0'" -> "'O', 3, code: '01'" [ label = "1" ];
"'ML', 2, code: '00'" -> "'M', 1, code: '000'" [ label = "0" ];
"'ML', 2, code: '00'" -> "'L', 1, code: '001'" [ label = "1" ];
"' KITP', 7, code: '1'" -> "' K', 3, code: '10'" [ label = "0" ];
"' KITP', 7, code: '1'" -> "'ITP', 4, code: '11'" [ label = "1" ];
"' K', 3, code: '10'" -> "' ', 1, code: '100'" [ label = "0" ];
"' K', 3, code: '10'" -> "'K', 2, code: '101'" [ label = "1" ];
"'ITP', 4, code: '11'" -> "'I', 2, code: '110'" [ label = "0" ];
"'ITP', 4, code: '11'" -> "'TP', 2, code: '111'" [ label = "1" ];
"'TP', 2, code: '111'" -> "'T', 1, code: '1110'" [ label = "0" ];
"'TP', 2, code: '111'" -> "'P', 1, code: '1111'" [ label = "1" ];
}

Codes of letters:
'O'(01) 'K'(101) 'I'(110) 'T'(1110) 'P'(1111) 'M'(000) 'L'(001) ' '(100)

Encoded string:
00001001011010110010111011111101110

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

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

struct ltcode
{
    unsigned long long frequency;
    unsigned char letter;
    string code = "";
};

void zeroset(ltcode *c)
{
    for (unsigned int i = 0; i < 256; ++i)
    {
        c[i].frequency = 0;
        c[i].letter = i;
    }
}

bool f(ltcode x, ltcode y)
{
    if (x.frequency != y.frequency) return x.frequency > y.frequency;
    else return x.letter > y.letter;
}

struct B
{
    string list;
    int i;
    
    int left;
    int right;
    
    string code = "";
    
    B()
    {
        list = "";
        i = 0;
    }
};

void print_binary_tree(int num, vector <B> &tree)
{
    if (tree[num].list.size() > 1)
    {
        cout << "\"'" << tree[num].list << "', " << tree[num].i << ", code: \'" << tree[num].code << "\'\" -> \"'" << tree[tree[num].left].list << "', " << tree[tree[num].left].i << ", code: \'" << tree[tree[num].left].code << "\'\" [ label = \"0\" ];\n";
        cout << "\"'" << tree[num].list << "', " << tree[num].i << ", code: \'" << tree[num].code << "\'\" -> \"'" << tree[tree[num].right].list << "', " << tree[tree[num].right].i << ", code: \'" << tree[tree[num].right].code << "\'\" [ label = \"1\" ];\n";
        print_binary_tree(tree[num].left, tree);
        print_binary_tree(tree[num].right, tree);
    }
}

void print_tree_graph(vector <B> &tree)
{
    cout << "digraph G {\n";
    print_binary_tree(tree.size()-1, tree);
    cout << "}\n";
}

void huffman_encoding_in(int num, string code, vector <B> &tree, ltcode *letter_codes)
{
    tree[num].code = code;
    if (tree[num].list.size() > 1)
    {
        huffman_encoding_in(tree[num].left, code+"0", tree, letter_codes);
        huffman_encoding_in(tree[num].right, code+"1", tree, letter_codes);
    }
    else
    {
        for (int j = 0; ; ++j)
        {
            if (letter_codes[j].letter == tree[num].list[0])
            {
                letter_codes[j].code = code;
                break;
            }
        }
    }
}

void huffman_encoding(vector <B> &sorted_tree, ltcode *letter_codes)
{
    huffman_encoding_in(sorted_tree.size()-1, "", sorted_tree, letter_codes);
}

int main() {
    unsigned char c;
    string S;
    ltcode count[256], stringlinks[256];
    zeroset(count);

    while (scanf("%c", &c))
    {
        if (c == '\n') break;
        S += c;
        ++count[c].frequency;
    }
    sort(count, count+256, f);
    
    vector <B> tree;
    B tmp;
    tmp.list = "0";
    int j = 0, letter_amount;
    for (j = 0; (count[j].frequency); ++j)
    {
        tmp.i = count[j].frequency;
        tmp.list[0] = count[j].letter;
        tree.push_back(tmp);
    }
    int maxsize = j-1, size;
    
    sort(tree.begin(), tree.end(), [] (B a, B b)
    {
        if (a.i != b.i) return (a.i < b.i);
        else return (a.list.size() < b.list.size());
    });
    
    for (j = 0; size < maxsize;)
    {
        tmp.list = tree[j].list + tree[j+1].list;
        tmp.i = tree[j].i + tree[j+1].i;
        tmp.left = j;
        tmp.right = j+1;
        
        size = tmp.list.size();
        
        tree.push_back(tmp);
        j += 2;
        sort(tree.begin()+j, tree.end(), [] (B a, B b)
        {
            if (a.i != b.i) return (a.i < b.i);
            else return (a.list.size() < b.list.size());
        }
        );
    }
    huffman_encoding(tree, count);
    print_tree_graph(tree);
    cout << "\nCodes of letters:\n";
    for (j = 0; (count[j].frequency); ++j)
    {
        cout << '\'' << count[j].letter << "\'(" << count[j].code << ")  ";
        stringlinks[count[j].letter].code = count[j].code;
    }
    cout << "\n\nEncoded string:\n";
    for (unsigned int i = 0; i < S.size(); ++i)
    {
        cout << stringlinks[S[i]].code;
    }
    cout << '\n';
    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

146

147

148

149

150

151

152

153

154

155

#include <iostream>

#include <algorithm>

#include <vector>

#include <string>

using namespace std;

struct ltcode

{

unsigned long long frequency;

unsigned char letter;

string code = "";

};

void zeroset(ltcode *c)

{

for (unsigned int i = 0; i < 256; ++i)

{

c[i].frequency = 0;

c[i].letter = i;

}

bool f(ltcode x, ltcode y)

{

if (x.frequency != y.frequency) return x.frequency > y.frequency;

else return x.letter > y.letter;

}

struct B

{

string list;

int i;

int left;

int right;

string code = "";

B()

{

list = "";

i = 0;

}

};

void print_binary_tree(int num, vector &tree)

{

if (tree[num].list.size() > 1)

{

cout << "\"'" << tree[num].list << "', " << tree[num].i << ", code: \'" << tree[num].code << "\'\" -> \"'" << tree[tree[num].left].list << "', " << tree[tree[num].left].i << ", code: \'" << tree[tree[num].left].code << "\'\" [ label = \"0\" ];\n";

cout << "\"'" << tree[num].list << "', " << tree[num].i << ", code: \'" << tree[num].code << "\'\" -> \"'" << tree[tree[num].right].list << "', " << tree[tree[num].right].i << ", code: \'" << tree[tree[num].right].code << "\'\" [ label = \"1\" ];\n";

print_binary_tree(tree[num].left, tree);

print_binary_tree(tree[num].right, tree);

}

void print_tree_graph(vector &tree)

{

cout << "digraph G {\n";

print_binary_tree(tree.size()-1, tree);

cout << "}\n";

}

void huffman_encoding_in(int num, string code, vector &tree, ltcode *letter_codes)

{

tree[num].code = code;

if (tree[num].list.size() > 1)

{

huffman_encoding_in(tree[num].left, code+"0", tree, letter_codes);

huffman_encoding_in(tree[num].right, code+"1", tree, letter_codes);

}

else

{

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

{

if (letter_codes[j].letter == tree[num].list[0])

{

letter_codes[j].code = code;

break;

}

void huffman_encoding(vector &sorted_tree, ltcode *letter_codes)

{

huffman_encoding_in(sorted_tree.size()-1, "", sorted_tree, letter_codes);

}

int main() {

unsigned char c;

string S;

ltcode count[256], stringlinks[256];

zeroset(count);

while (scanf("%c", &c))

{

if (c == '\n') break;

S += c;

++count[c].frequency;

}

sort(count, count+256, f);

vector tree;

B tmp;

tmp.list = "0";

int j = 0, letter_amount;

for (j = 0; (count[j].frequency); ++j)

{

tmp.i = count[j].frequency;

tmp.list[0] = count[j].letter;

tree.push_back(tmp);

}

int maxsize = j-1, size;

sort(tree.begin(), tree.end(), [] (B a, B b)

{

if (a.i != b.i) return (a.i < b.i);

else return (a.list.size() < b.list.size());

});

for (j = 0; size < maxsize;)

{

tmp.list = tree[j].list + tree[j+1].list;

tmp.i = tree[j].i + tree[j+1].i;

tmp.left = j;

tmp.right = j+1;

size = tmp.list.size();

tree.push_back(tmp);

j += 2;

sort(tree.begin()+j, tree.end(), [] (B a, B b)

{

if (a.i != b.i) return (a.i < b.i);

else return (a.list.size() < b.list.size());

}

);

}

huffman_encoding(tree, count);

print_tree_graph(tree);

cout << "\nCodes of letters:\n";

for (j = 0; (count[j].frequency); ++j)

{

cout << '\'' << count[j].letter << "\'(" << count[j].code << ") ";

stringlinks[count[j].letter].code = count[j].code;

}

cout << "\n\nEncoded string:\n";

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

{

cout << stringlinks[S[i]].code;

}

cout << '\n';

return 0;

}

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

Для начала считываем посимвольно строку и запоминаем её, параллельно запоминая частоты появлений символов в ней в массиве count. Останавливаем считывание, когда встречается endl. После этого отсортировуем массив count в порядке убывания частот.

После этого элементы массива count, которые имеют ненулевую частоту, преобразовываем в элементы вектора tree (при этом символы конвертируются в строки), который после сортируется в порядке возрастания частот. Затем обрабатываем массив по алгортиму Хаффмана, объединяя элементы вектора с номерами [latex]j[/latex], [latex]j+1[/latex] в новый (который будет представлять собой структуру из конкатенации строк ранее упомянутых элементов и суммы их частот, а так же номеров его «предков»). После этого вектор вновь сортируется по частотам/суммам частот в порядке возрастания начиная с номера[latex]j+2[/latex], при этом элементы, которые имеют больший размер строк будут иметь меньший приоритет.

Такой алгоритм приводит к тому, что элементы с меньшей частотой/суммой частот не затрагиваются при добавлении новых, и система индексов (условных указателей на «предков») не нарушается.

После этого, используя поиск в глубину, кодируем элементы массива tree, начиная с последнего (строка которого в результате использования алгоритма всегда оказывается объединением всех символов). Остальная часть решения поставленной задачи — вопрос техники.

Ссылки

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

Related Images:

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

27/06/2016 by Аня Шохина

Задача

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

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

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

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

Выведите через пробел числа [latex]d_1,d_2,[/latex][latex]\ldots[/latex][latex],d_i[/latex], где [latex]d_i[/latex] равно[latex]-1[/latex], если путей между [latex]x[/latex] и [latex]i[/latex] нет, в противном случае это минимальное расстояние между [latex]x[/latex] и [latex]i[/latex].

Тесты

Входные данные	Выходные данные
3 1 0 1 0 0 0 0 0 0 0	0 1 -1
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 1 0 1 0 1 0 1 0 1 0	0 1 2

Реализация

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    const int inf=4000; // задаем бесконечность 
    int n, start_position, x; // n-количество вершин,х используем для приема матрицы смежности 
    cin>>n>>start_position;
    start_position--; // в условии счет начинается с единицы, а в программе с нуля 
    vector <int> verges [1001]; //задаем массив векторов, где i-ый вектор содержит в себе номера вершин в которые можно попасть с i-ой вершины
    for (int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin>>x;
            if (x==1){
                verges[i].push_back(j);
            }
        }
    }
    bool *used = new bool [n];
    for (int i=0; i<n; i++){
        used[i]=false;
    }
    int *distances = new int [n]; //задаем массив расстояний, где i-ый элемент - это расстояние от исходной вершины до  i-ой
    for (int i=0; i<n; i++){
        distances[i]=inf; 
    }
    distances[start_position] = 0;
    for (int i=0; i<n; i++){ //ищем вершину с наименьшей длиной пути до заданной вершины 
        int minimum=inf;
        int position = 0;
        for (int j=0; j<n; j++){
            if (distances[j]<minimum && !used[j]){
                minimum=distances[j];
                position=j;
            }
        }
        used[position]=true; //запоминаем, что применили алгоритм для вершины 
        for (int i=0; i<verges[position].size(); i++){ // применяем алгоритм Дейкстры 
            distances[verges[position][i]] = min(distances[verges[position][i]], (distances[position]+1));
        }
    }
    for (int i=0; i<n; i++) {
        cout<<((distances[i]==inf)?-1:distances[i])<<" ";
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int main() {

const int inf=4000; // задаем бесконечность

int n, start_position, x; // n-количество вершин,х используем для приема матрицы смежности

cin>>n>>start_position;

start_position--; // в условии счет начинается с единицы, а в программе с нуля

vector <int> verges [1001]; //задаем массив векторов, где i-ый вектор содержит в себе номера вершин в которые можно попасть с i-ой вершины

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

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

cin>>x;

if (x==1){

verges[i].push_back(j);

}

bool *used = new bool [n];

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

used[i]=false;

}

int *distances = new int [n]; //задаем массив расстояний, где i-ый элемент - это расстояние от исходной вершины до i-ой

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

distances[i]=inf;

}

distances[start_position] = 0;

for (int i=0; i<n; i++){ //ищем вершину с наименьшей длиной пути до заданной вершины

int minimum=inf;

int position = 0;

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

if (distances[j]<minimum && !used[j]){

minimum=distances[j];

position=j;

}

used[position]=true; //запоминаем, что применили алгоритм для вершины

for (int i=0; i<verges[position].size(); i++){ // применяем алгоритм Дейкстры

distances[verges[position][i]] = min(distances[verges[position][i]], (distances[position]+1));

}

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

cout<<((distances[i]==inf)?-1:distances[i])<<" ";

}

return 0;

}

Засчитанное решение на e-olimp.com

Код на ideone.com

Решение

Для решения данной задачи необходимо применить алгоритм Дейкстры . А именно, мы храним в массиве текущую длину наиболее короткого пути из заданной вершины во все остальные вершины графа. Положим, что изначально длина такого пути равна бесконечности ( при реализации просто используем достаточно большое число). А длина пути из заданной вершины до самой себя равна нулю. Обозначим, что вершина может быть помечена или не помечена. Изначально все вершины являются не помеченными. Далее выбираем вершину [latex]v[/latex] с наименьшей длиной пути до заданной вершины и помечаем ее. Тогда просматриваем все ребра, исходящие из вершины [latex]v[/latex]. Пусть эти ребра имеют вид [latex]\left ( v,t_0 \right )[/latex]. Тогда для каждой такой вершины [latex]t_0[/latex] пытаемся найти наиболее коротки путь из заданной вершины. После чего снова выбираем еще не помеченную вершину и проделываем вышеописанный алгоритм снова до тех пор, пока не останется не помеченных вершин. Найденные расстояния и будут наименьшими.

Related Images:

e-olymp 1948. Топологическая сортировка

06/06/2016 by Грешилов Константин

Условие:
Дан ориентированный невзвешенный граф. Необходимо топологически отсортировать его вершины.

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

В первой строке содержатся количество вершин [latex]n[/latex] (1 ≤ [latex]n[/latex] ≤ 100000) и количество рёбер [latex]m[/latex] (1 ≤[latex]m[/latex] ≤ 100000) в графе. В следующих [latex]m[/latex] строках перечислены рёбра графа, каждое из которых задаётся парой чисел — номерами начальной и конечной вершины.

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

Вывести любую топологическую сортировку графа в виде последовательности номеров вершин. Если граф невозможно топологически отсортировать, то вывести -1.

Тесты:

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

Решение:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool cyclic (int v, int &cycle_st, vector <int> *graph, vector <int> &color ) { //проверка графа на цикличность
    color[v] = 1;
    for (size_t i = 0; i < graph[v].size(); ++i) {
        int to = graph[v][i];
        if (color[to] == 0) { //если в вершину не входили ни разу
            if (cyclic (to, cycle_st, graph,  color))  return true;
        }
        else if (color[to] == 1) { //если в указанную вершину ранее входили, то значит, что найден цикл
            cycle_st = to; // и меняем значение индикатора 
            return true; 
        }
    }
    color[v] = 2; //указываем, что в вершину больше ни разу входить не будем
    return false;
}
void dfs (int v, vector <int> *graph, vector<bool> &used, vector <int> &answer) {
    used[v] = true; //указываем, что использовали данную вершину
    for (int i=0; i < graph[v].size(); i++) {
        int to = graph[v][i]; //по списку проходим по всем вершинам, к которым можно пройти от вершины v
        if (!used[to])//и если вершину не рассматривали, то применяем алгоритм поиска в глубину для неё
            dfs (to, graph, used, answer);
    }
    answer.push_back (v+1); // заносим вершину в вектор, хранящий результат
}
 
void topological_sort(int n, vector <int> *graph, vector<bool> &used, vector <int> &answer) {
    for (int i = 0; i < n; i++) //указываем, что ни одна вершина не была использована
        used[i] = false;
    for (int i = 0; i < n; i++)
        if (!used[i]) //если в ходе предыдущий операций вершина не использовалась
            dfs (i, graph, used, answer); // то вызываем для неё алгоритм поиска в глубину
    reverse (answer.begin(), answer.end());
}

int main() {
    int n, m; // число вершин и ребер
    cin >> n >> m;
    int a, b;
    vector <int> graph[100001]; // граф
    vector <bool> used (n);
    vector<int> answer;
    vector<int> color (n,0); //массив, хранящий кол-во посещений для данной вершины.
    int cycle_st = -1;
    for (int i = 0; i < m; i++){
            cin >> a >> b;
            graph[a-1].push_back(b-1);
        }
    for (int i = 0; i < n; i++){
        if (cyclic(i, cycle_st, graph, color)) //проверка графа на ацикличность
            break;
    }
    if (cycle_st != -1){ 
        cout << "-1";
    }
    else{
        topological_sort(n, graph, used, answer);
        for (int i = 0; i < answer.size(); i++)
        {
            cout << answer[i] << " "; 
        }
        cout << endl;
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

bool cyclic (int v, int &cycle_st, vector <int> *graph, vector <int> &color ) { //проверка графа на цикличность

color[v] = 1;

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

int to = graph[v][i];

if (color[to] == 0) { //если в вершину не входили ни разу

if (cyclic (to, cycle_st, graph, color)) return true;

}

else if (color[to] == 1) { //если в указанную вершину ранее входили, то значит, что найден цикл

cycle_st = to; // и меняем значение индикатора

return true;

}

color[v] = 2; //указываем, что в вершину больше ни разу входить не будем

return false;

}

void dfs (int v, vector <int> *graph, vector<bool> &used, vector <int> &answer) {

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

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

int to = graph[v][i]; //по списку проходим по всем вершинам, к которым можно пройти от вершины v

if (!used[to])//и если вершину не рассматривали, то применяем алгоритм поиска в глубину для неё

dfs (to, graph, used, answer);

}

answer.push_back (v+1); // заносим вершину в вектор, хранящий результат

}

void topological_sort(int n, vector <int> *graph, vector<bool> &used, vector <int> &answer) {

for (int i = 0; i < n; i++) //указываем, что ни одна вершина не была использована

used[i] = false;

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

if (!used[i]) //если в ходе предыдущий операций вершина не использовалась

dfs (i, graph, used, answer); // то вызываем для неё алгоритм поиска в глубину

reverse (answer.begin(), answer.end());

}

int main() {

int n, m; // число вершин и ребер

cin >> n >> m;

int a, b;

vector <int> graph[100001]; // граф

vector <bool> used (n);

vector<int> answer;

vector<int> color (n,0); //массив, хранящий кол-во посещений для данной вершины.

int cycle_st = -1;

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

cin >> a >> b;

graph[a-1].push_back(b-1);

}

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

if (cyclic(i, cycle_st, graph, color)) //проверка графа на ацикличность

break;

}

if (cycle_st != -1){

cout << "-1";

}

else{

topological_sort(n, graph, used, answer);

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

{

cout << answer[i] << " ";

}

cout << endl;

}

return 0;

}

Описание решения:

Для решения данной задачи необходимо было воспользоваться алгоритмом топологической сортировки, посредством поиcка в глубину. Чтобы применить данный алгоритм, необходимо было проверить граф на ацикличность с помощью алгоритма поиска в глубину. Это было реализовано функцией [latex]cyclic[/latex], которая проходила по всему графу в поиске цикла. Если цикл был найден, то функция меняла значение переменной [latex]cycle_st[/latex]. Далее, если цикл был найден, то программа выводить -1, иначе применяется алгоритм топологической сортировки, реализованный в двух функциях:

void dfs (int v, vector <int> *graph, vector<bool> &used, vector <int> &answer)

20	void dfs (int v, vector <int> *graph, vector<bool> &used, vector <int> &answer)

void topological_sort(int n, vector <int> *graph, vector<bool> &used, vector <int> &answer)

30	void topological_sort(int n, vector <int> *graph, vector<bool> &used, vector <int> &answer)

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

Засчитанное решение на e-olymp.com.

Код решения на ideone.com.

Related Images:

e-olymp 2401. Обход в ширину

31/05/2016 by Андрей Яроцкий

Задача 2401

Условие

Дан неориентированный граф. В нём необходимо найти расстояние от одной заданной вершины до другой.

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

В первой строке содержится три натуральных числа [latex]n, s[/latex] и [latex]f (1 [/latex] [latex]\le[/latex] [latex]s, f[/latex] [latex]\le[/latex] [latex]n[/latex] [latex]\le[/latex] [latex]100)[/latex] — количество вершин в графе и номера начальной и конечной вершин соответственно. Далее в n строках задана матрица смежности графа. Если значение в [latex]j[/latex]-м элементе [latex]i[/latex]-й строки равно [latex]1[/latex], то в графе есть направленное ребро из вершины [latex]i[/latex] в вершину [latex]j[/latex].

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

Вывести минимальное расстояние от начальной вершины до конечной. Если пути не существует, выведите [latex]0[/latex].

Тесты

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

#include <iostream>
using namespace std;

struct node{
    int value;
    node * next;
    node(int v, node * n = NULL){
        value = v;
        next = n;
    }
};
 
struct queue{ // Структура очередь
    node * start;
    node * finish;
    int len = 0;
    queue(node * s = NULL, node * f = NULL){
        start = s;
        finish = f;
    }
    string push(int n){
        if(len == 0){
            node * new_node = new node(n,finish);
            start = new_node;
            finish = new_node;
        }else{
            node * new_node = new node(n,NULL);
            start -> next = new_node;
            start = new_node;
        }
        len++;
        return "ok";
    }
    int pop(){
        int v = finish -> value;
        finish = finish -> next;
        len--;
        return v;
    }
    int front(){
        return finish -> value;
    }
    int size(){
        return len;
    }
};

int main() {
    int n, s, f;
    cin >> n >> s >> f;
    int graph[n][n];
    int dist[n]; // Массив расстояний от начальной до i-ой вершины
    bool used[n];
    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++){
        dist[i] = 0;
        used[i] = false;
    }
    queue vertex; // Очередь вершин
    vertex.push(s-1);
    used[s-1] = true;
    while(vertex.size() != 0){
        int v = vertex.front();
        for(int i = 0; i < n; i++){
            if(graph[v][i] == 1 && used[i] == false){
                vertex.push(i);
                dist[i] = dist[v] + 1; 
                used[i] = true; // i-ая вершина пройдена и не будет корректироваться позже
            }
        }
        used[v] = true;
        vertex.pop();
    }
    cout << dist[f-1];
    return 0;
}

#include <iostream>

using namespace std;

struct node{

int value;

node * next;

node(int v, node * n = NULL){

value = v;

next = n;

}

};

struct queue{ // Структура очередь

node * start;

node * finish;

int len = 0;

queue(node * s = NULL, node * f = NULL){

start = s;

finish = f;

}

string push(int n){

if(len == 0){

node * new_node = new node(n,finish);

start = new_node;

finish = new_node;

}else{

node * new_node = new node(n,NULL);

start -> next = new_node;

start = new_node;

}

len++;

return "ok";

}

int pop(){

int v = finish -> value;

finish = finish -> next;

len--;

return v;

}

int front(){

return finish -> value;

}

int size(){

return len;

}

};

int main() {

int n, s, f;

cin >> n >> s >> f;

int graph[n][n];

int dist[n]; // Массив расстояний от начальной до i-ой вершины

bool used[n];

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++){

dist[i] = 0;

used[i] = false;

}

queue vertex; // Очередь вершин

vertex.push(s-1);

used[s-1] = true;

while(vertex.size() != 0){

int v = vertex.front();

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

if(graph[v][i] == 1 && used[i] == false){

vertex.push(i);

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

used[i] = true; // i-ая вершина пройдена и не будет корректироваться позже

}

used[v] = true;

vertex.pop();

}

cout << dist[f-1];

return 0;

}

Решение

Для решения данной задачи необходимо использовать алгоритм «Поиск в ширину». Суть данного алгоритма полагает в том, что все вершины, начиная с начальной, помещаются в структуру очередь [latex](queue)[/latex] в порядке удаления от начальной вершины. По мере заполнения очереди, каждой вершине приписывается величина расстояния [latex](dist)[/latex] от начальной вершины, после чего соответствующая вершина помечается как пройденная [latex](used)[/latex] и её расстояние от начальной вершины более не переписывается даже при повторном просмотре. Таким образом, каждой вершине, для которой существует путь, соединяющий её с начальной вершиной, сопоставляется минимальное расстояние от нее до начальной вершины. Если такого пути не существует, расстояние остается равным нулю. Подробней об этом алгоритме можно прочесть здесь

Ссылки

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

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

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

Related Images:

e-olymp 1455. Цикл

12/05/2016 by Катя Писова

Задача

Дан граф. Определить, есть ли в нем цикл отрицательного веса, и если да, то вывести его.

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

Первая строка содержит количество вершин графа n (1 ≤ n ≤ 100). В следующих n строках находится по n чисел — матрица смежности графа. Веса ребер не превышают по модулю 10000. Если ребра нет, соответствующее значение равно 100000.

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

В первой строке выведите «YES«, если цикл существует, или «NO» в противном случае. При наличии цикла выведите во второй строке количество вершин в нем (считая одинаковыми первую и последнюю) и в третьей строке — вершины, входящие в этот цикл в порядке обхода. Если циклов несколько — выведите любой.

Тесты

Входные данные	Выходные данные:
2 0 -1 -1 0	YES 3 1 2 1
4 0 2 0 9 2 0 6 0 0 6 0 -3 9 0 -3 0	YES 3 3 4 3
3 0 2 3 2 0 1 3 1 0	NO

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

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

struct edge{
    int from, to, cost;
};
const int INF = 1e9;;

int main(){
    int n;
    cin >> n;
    vector <edge> E;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            int x;
            cin >> x;
            if(x != 0 && x != 100000){
                E.push_back({i,j,x});
            }
        }
    }
    int x ;
    vector<int> d(n, INF), p(n, -1);
    d[0] = 0;
    for(int i = 0; i < n; i++){
        x = -1;
        for(int j = 0; j < E.size(); j++){
            int from = E[j].from;
            int to = E[j].to;
            int cost = E[j].cost;
            if(d[to] > d[from] + cost ){
                d[to] = max(d[from] + cost, -INF);
                p[to] = from;
                x = to;
            }
        }
    }
    if(x == -1){
        cout << "NO" << endl;
    }else{
        int y = x;
        for(int i = 0; i < n; i++){
            y = p[y];
        }
        vector <int> path;
        for(int cur = y;; cur = p[cur]){
            path.push_back(cur);
            if(cur == y && path.size() > 1){
                break;
            }
        }
        reverse(path.begin(), path.end());
        cout << "YES" << endl;
        cout << path.size() << endl;
        for(int i = 0; i < path.size(); i++){
            cout << path[i] + 1;
            if(i != path.size()-1){
                cout << ' ';
            }
        }
        cout << endl;
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

struct edge{

int from, to, cost;

};

const int INF = 1e9;;

int main(){

int n;

cin >> n;

vector <edge> E;

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

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

int x;

cin >> x;

if(x != 0 && x != 100000){

E.push_back({i,j,x});

}

int x ;

vector<int> d(n, INF), p(n, -1);

d[0] = 0;

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

x = -1;

for(int j = 0; j < E.size(); j++){

int from = E[j].from;

int to = E[j].to;

int cost = E[j].cost;

if(d[to] > d[from] + cost ){

d[to] = max(d[from] + cost, -INF);

p[to] = from;

x = to;

}

if(x == -1){

cout << "NO" << endl;

}else{

int y = x;

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

y = p[y];

}

vector <int> path;

for(int cur = y;; cur = p[cur]){

path.push_back(cur);

if(cur == y && path.size() > 1){

break;

}

reverse(path.begin(), path.end());

cout << "YES" << endl;

cout << path.size() << endl;

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

cout << path[i] + 1;

if(i != path.size()-1){

cout << ' ';

}

cout << endl;

}

return 0;

}

Алгоритм решения:

Для решения данной задачи задействован алгоритм Беллмана-Форда, который позволяет проверить наличие или отсутствие цикла отрицательного веса в графе, а при его наличии — найти один из таких циклов. Создадим вектор, который будет содержать в себе элементы матрицы смежности графа. По определению смежных вершин графа, учитывая условие задачи (если ребра нет, соответствующее значение равно [latex]100000[/latex]), заполним этот вектор. Далее будем использовать алгоритм Беллмана-Форда. Если алгоритм даст отрицательный ответ на вопрос задачи, то выводим NO. Если цикл все-таки существует, то выводим YES. В вектор записываем вершины, входящие в цикл отрицательного веса. Далее выводим их количество, а затем и сами вершины в порядке обхода.

Для получения подробной информации об алгоритме Беллмана-Форда можно перейти по данной ссылке
Ссылка на засчитанное решение на e-olymp
Ссылка на условие задачи
Ссылка на решение задачи на ideone.com

Related Images:

e-olymp 5071. Проверка на неориенитрованность

29/04/2016 by Кудымовская Вика

Задача. Проверка на неориенитрованность

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

По заданной квадратной матрице [latex]n\times n[/latex] из нулей и единиц определите, может ли данная матрица быть матрицей смежности простого неориентированного графа.

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

Входной файл содержит число [latex]n(1\leq n\leq 100)[/latex] — размер матрицы, и затем [latex]n[/latex] строк по [latex]n[/latex] чисел, каждое из которых равно [latex]0[/latex] или [latex]1[/latex] — саму матрицу.

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

Выведите в выходной файл YES если приведенная матрица может быть матрицей смежности простого неориентированного графа и NO в противном случае.

Также условие задачи можно посмотреть здесь.

Тестирование

№	Входные данные	Выходные данные
1.	3 0 1 1 1 0 1 1 1 0	YES
2.	3 0 1 0 1 0 1 1 1 0	NO
3.	3 0 1 0 1 1 1 0 1 0	NO

Реализация

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    int n; 
    cin >> n;
    vector<int> G(n*n);
    for (int i = 0; i < G.size(); i++) 
    { 
        cin >> G[i];
    }
    int j = 0, c = 0, s = 0;
    /*с - счетчик циклов, сигнализирует о завершении текущего цикла сравнения 
    элементов i строки и j столбца; j - служит индексом для элементов столбца;
    s - счетчик столбцов, служит для задания нового начального значения индексу 
    j при переходе к следующему циклу сравнения элементов i строки и j столбца;*/
    bool f = true;              
    for (int i = 0; i < n*n; i++)//задаем цикл по всему массиву
    {
        if (G[i] != G[j]) { f=false; break; }
        if (c == n - 1)             
        {                   
            c = 0; s++; j = s;      
        }
        /*если уже сравнили n-1 строку и столбец, обнуляем c, увеличиваем s 
        и присваиваем его как новое начальное значение для индекса элементов столбца j*/
        else
        {
            j = j + n;//на каждом шаге устанавливаем индекс для элемента столбца
            c++;                
        }
    }
    for (int i = 0; i < n*n; i = i + n + 1)
    /*цикл для определения равенства нулю элементов главной диагонали - индекс 
    увеличивается на n+1 на каждом шаге*/
    {                   
        if (G[i] != 0) { f = false; break; }    
    }
    if (f) cout << "YES";
    else cout << "NO";
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main()

{

int n;

cin >> n;

vector<int> G(n*n);

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

{

cin >> G[i];

}

int j = 0, c = 0, s = 0;

/*с - счетчик циклов, сигнализирует о завершении текущего цикла сравнения

элементов i строки и j столбца; j - служит индексом для элементов столбца;

s - счетчик столбцов, служит для задания нового начального значения индексу

j при переходе к следующему циклу сравнения элементов i строки и j столбца;*/

bool f = true;

for (int i = 0; i < n*n; i++)//задаем цикл по всему массиву

{

if (G[i] != G[j]) { f=false; break; }

if (c == n - 1)

{

c = 0; s++; j = s;

}

/*если уже сравнили n-1 строку и столбец, обнуляем c, увеличиваем s

и присваиваем его как новое начальное значение для индекса элементов столбца j*/

else

{

j = j + n;//на каждом шаге устанавливаем индекс для элемента столбца

c++;

}

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

/*цикл для определения равенства нулю элементов главной диагонали - индекс

увеличивается на n+1 на каждом шаге*/

{

if (G[i] != 0) { f = false; break; }

}

if (f) cout << "YES";

else cout << "NO";

return 0;

}

Алгоритм решения

Чтобы введённая матрица была матрицей смежности простого неориентированного графа, она должна, во-первых, быть симметричной, то есть элементы на соответствующих позициях должны быть равны между собой: [latex]a[i][j]=a[j][i][/latex]. Во-вторых, необходимо, чтобы элементы главной диагонали матрицы равнялись нулю. Таким образом, нам нужно проверить, выполняются ли указанные условия.
Создаём переменную f типа bool. Изначально f=true. Если при проверке на симметричность и равенство нулю главной диагонали хоть одно значение элемента матрицы не удовлетворяет условию, флаг устанавливается в «ложь» и происходит выход из цикла проверки. Это означает соответственно, что введённая матрица не является матрицей смежности неориентированного графа, — на экран выводится «NO». Если же оба условия выполняются, приведённая матрица — матрица смежности. Выводим «YES».

Подробнее о графах и матрице смежности можно прочесть, используя следующие интернет-ресурсы:

Для запроса на выполнение следует перейти по ссылке.

Ссылка на засчитанное решение на e-olymp.com.

Related Images:

e-olymp 978. Получи дерево

26/04/2016 by Павел Загинайло

Задача с сайта e-olymp.com.

Условие

Дан связный неориентированный граф без петель и кратных ребер. Разрешается удалять из него ребра. Требуется получить дерево.

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

Первая строка содержит количество вершин [latex]n[/latex] (1 ≤ [latex]n[/latex] ≤ 100) и количество ребер [latex]m[/latex] графа. Следующие [latex]m[/latex] пар чисел задают ребра графа. Гарантируется, что граф связный.

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

Выведите [latex]n — 1[/latex] пару чисел — ребра, которые войдут в дерево. Ребра можно выводить в любом порядке.

Код

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


/*
Объявляем структуру Ребро, которой будем пользоваться для построения графа и дерева
*/
struct edge{
    int x, y; //вершины
    edge(){}
    edge(int a, int b){
        x = a;
        y = b;
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    
    vector <edge> graph (m); //ребра исходного графа
    vector <edge> tree; //ребра дерева
    vector <int> variety (n); //множество вершин
    
    /*
    variety[n] = m - вершина n принадлежит множеству m.
    Следующий цикл определяет для каждой вершины свое множество
    */
    for (int i = 0; i < n; i++){
        variety[i] = i;
    }
    
    /*
    Заполняем ребра исходного графа значениями из стандартного ввода
    */
    for (int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        graph[i].x = a;
        graph[i].y = b;
    }
    
    /*
    Проверяем вершины каждого ребра. 
    Если вершины не принадлежат одному и тому же множеству, 
    но такое ребро добавляем в наше дерево, а вершины помещаем в одно множество
    */
    for (int i = 0; i < m; i++){
        int a = graph[i].x;
        int b = graph[i].y;
        if (variety[a] != variety[b]){
            tree.push_back(graph[i]);
            int old_variety = variety[b], new_variety = variety[a];
            for (int j = 0; j < n; j++){
                if (variety[j] == old_variety){
                    variety[j] = new_variety;
                }
            }
            
            
            
        }
    }

    
    for(int i = 0; i < n - 1; i++){ //по принципу построения дерева, оно содержит n-1 ребро
        cout << tree[i].x << " " << tree[i].y;
        if (i != n-2){
            cout << endl;
        }
    }
    return 0;
}

#include <algorithm>

#include <iostream>

#include <vector>

using namespace std;

Объявляем структуру Ребро, которой будем пользоваться для построения графа и дерева

struct edge{

int x, y; //вершины

edge(){}

edge(int a, int b){

x = a;

y = b;

}

};

int main() {

int n, m;

cin >> n >> m;

vector <edge> graph (m); //ребра исходного графа

vector <edge> tree; //ребра дерева

vector <int> variety (n); //множество вершин

variety[n] = m - вершина n принадлежит множеству m.

Следующий цикл определяет для каждой вершины свое множество

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

variety[i] = i;

}

Заполняем ребра исходного графа значениями из стандартного ввода

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

int a, b;

cin >> a >> b;

graph[i].x = a;

graph[i].y = b;

}

Проверяем вершины каждого ребра.

Если вершины не принадлежат одному и тому же множеству,

но такое ребро добавляем в наше дерево, а вершины помещаем в одно множество

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

int a = graph[i].x;

int b = graph[i].y;

if (variety[a] != variety[b]){

tree.push_back(graph[i]);

int old_variety = variety[b], new_variety = variety[a];

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

if (variety[j] == old_variety){

variety[j] = new_variety;

}

for(int i = 0; i < n - 1; i++){ //по принципу построения дерева, оно содержит n-1 ребро

cout << tree[i].x << " " << tree[i].y;

if (i != n-2){

cout << endl;

}

return 0;

}

Тесты

Ввод	Вывод
4 4 1 2 2 3 3 4 4 1	1 2 2 3 3 4
6 7 1 2 2 3 3 4 4 5 5 6 6 1	1 2 2 3 3 4 4 5 5 6
6 5 1 2 2 3 3 4 4 5 5 6	1 2 2 3 3 4 4 5 5 6
4 5 4 3 2 4 2 3 1 2 1 3	4 3 2 4 1 2
6 9 1 2 1 3 1 5 2 5 2 4 3 5 3 6 4 5 5 6	1 2 1 3 1 5 2 4 3 6

Решение

Учитывая то, что по условию задачи нам дан связный неориентированный граф без петель и кратных ребер и то, что любое дерево с [latex]n[/latex] вершинами содержит [latex]n-1[/latex] ребро, то для получения дерева нужно удалить столько ребер, пока не останется [latex]n-1[/latex] ребро.

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

Засчитанное решение на e-olymp

Код на ideone.com

UPD: обновил код, тесты, описание решения и ссылки.

Related Images:

e-olymp 4003. Топологическая сортировка

26/03/2016 by Сплошнов Кирилл

Задача взята отсюда.

Условие

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

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

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

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

Вывести любую топологическую сортировку графа в виде последовательности номеров вершин. Если граф невозможно топологически отсортировать, требуется вывести [latex]-1[/latex].

Решение

Для решения использовался алгоритм топологической сортировки методом поиска в глубину (подробнее в комментариях к коду). Функция bool dfs() (поиск в глубину) также проверяет, цикличен ли граф, т.к. по условию он может как содержать, так и не содержать циклы. Результат сортировки заносим в вектор result, потом выводим его элементы по порядку.

Тесты

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

Код

#include <iostream>
#include <vector>
#include <algorithm>
#define WHITE 0 //вершина не посещена
#define GREY 1 //вершина обрабатывается
#define BLACK 2 //вершина обработана
using namespace std;

bool dfs (int v, vector<int>* vertex, int* state, vector<int> &result, int size) //возвращает true или false в зависимости от того, был ли найден цикл
{
	state[v] = GREY; //отмечаем, что вершина в процессе обработки
	for (int i = 0; i < vertex[v].size(); i++) //для каждой вершины, в которую можно попасть из данной
	{
		int dest = vertex[v].at(i);
		if (state[dest] == WHITE) //если еще не посетили - запускаем поиск в глубину, возвращаем true, если далее был найден цикл
		{
			if (dfs(dest, vertex, state, result, size))
				return true;
		}
		else if (state[dest] == GREY) //если из вершины можно попасть туда, где мы уже были при данном порядке обхода - найден цикл
		{
			return true;
		}
	}
    //если цикл не найден:
	state[v] = BLACK; //помечаем вершину как обработанную
	result.push_back(v+1); //помещаем ее номер (со сдвигом на 1, из-за разницы в нумерациях) в вектор-результат сортировки
	return false;
}

void topologicalSort(vector<int>* vertex, int* state, vector<int> &result, int size)
{
	for (int i = 0; i < size; i++) //для каждой вершины графа
	{
		if (state[i] == WHITE) //если она еще не посещена
		{
			bool cyclic = dfs(i, vertex, state, result, size); //вызываем для нее поиск в глубину
			if (cyclic) //если нашли цикл, возвращаем единственное значение -1 (по условию)
			{
				result.clear();
				result.push_back(-1);
				return;
			}
		}
	}
	reverse(result.begin(), result.end()); //вершины добавляются в вектор в порядке, противоположном топологической сортировке, так что нужно вызвать для вектора reverse()
}

int main() 
{
	ios::sync_with_stdio(false); 
	int n, m;
	cin >> n >> m;
	vector<int> vertex[n]; //сам граф
	int state[n]; //массив состояний вершин
	vector<int> result;
	fill (state, state + n, WHITE); //изначально ни одна вершина не посещена
	for (int i = 0; i < n; i++)
	{
		int begin, end;
		cin >> begin >> end;
		vertex[begin-1].push_back(end-1);
	}
	topologicalSort(vertex, state, result, n); //сортируем граф
	for (int i = 0; i < result.size(); i++)
		cout << result.at(i) << " ";
	return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

#define WHITE 0 //вершина не посещена

#define GREY 1 //вершина обрабатывается

#define BLACK 2 //вершина обработана

using namespace std;

bool dfs (int v, vector<int>* vertex, int* state, vector<int> &result, int size) //возвращает true или false в зависимости от того, был ли найден цикл

{

state[v] = GREY; //отмечаем, что вершина в процессе обработки

for (int i = 0; i < vertex[v].size(); i++) //для каждой вершины, в которую можно попасть из данной

{

int dest = vertex[v].at(i);

if (state[dest] == WHITE) //если еще не посетили - запускаем поиск в глубину, возвращаем true, если далее был найден цикл

{

if (dfs(dest, vertex, state, result, size))

return true;

}

else if (state[dest] == GREY) //если из вершины можно попасть туда, где мы уже были при данном порядке обхода - найден цикл

{

return true;

}

//если цикл не найден:

state[v] = BLACK; //помечаем вершину как обработанную

result.push_back(v+1); //помещаем ее номер (со сдвигом на 1, из-за разницы в нумерациях) в вектор-результат сортировки

return false;

}

void topologicalSort(vector<int>* vertex, int* state, vector<int> &result, int size)

{

for (int i = 0; i < size; i++) //для каждой вершины графа

{

if (state[i] == WHITE) //если она еще не посещена

{

bool cyclic = dfs(i, vertex, state, result, size); //вызываем для нее поиск в глубину

if (cyclic) //если нашли цикл, возвращаем единственное значение -1 (по условию)

{

result.clear();

result.push_back(-1);

return;

}

reverse(result.begin(), result.end()); //вершины добавляются в вектор в порядке, противоположном топологической сортировке, так что нужно вызвать для вектора reverse()

}

int main()

{

ios::sync_with_stdio(false);

int n, m;

cin >> n >> m;

vector<int> vertex[n]; //сам граф

int state[n]; //массив состояний вершин

vector<int> result;

fill (state, state + n, WHITE); //изначально ни одна вершина не посещена

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

{

int begin, end;

cin >> begin >> end;

vertex[begin-1].push_back(end-1);

}

topologicalSort(vertex, state, result, n); //сортируем граф

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

cout << result.at(i) << " ";

return 0;

}

Ссылки

Код на ideaone.

Засчитанное решение на e-olymp.

Наглядное объяснение топологической сортировки здесь.

Related Images:

e-olymp 1454. Лабиринт знаний

28/06/2015 by Ковальський Олександр Дмитрович

Задача

В Летней Компьютерной Школе (ЛКШ) построили аттракцион «Лабиринт знаний». Лабиринт представляет собой n комнат, занумерованных от 1 до n, между некоторыми из которых есть двери. Когда человек проходит через дверь, показатель его знаний изменяется на определенную величину, фиксированную для данной двери. Вход в лабиринт находится в комнате 1, выход — в комнате n. Каждый ученик проходит лабиринт ровно один раз и попадает в ту или иную учебную группу в зависимости от количества набранных знаний (при входе в лабиринт этот показатель равен нулю). Ваша задача показать наилучший результат.

Пример

Входные данные	Выходные данные
2 2 1 2 5 1 2 -5	5
5 5 1 2 5 2 4 5 4 5 5 3 3 5 2 3 5	15
3 3 1 2 5 1 2 -5 2 2 6	🙁
3 3 1 2 2 2 3 3 3 1 4	🙂

Решение

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

struct edge
	{
		int start,finish,cost;
	};
	
int main()
	{
		int n,m;
		cin>>n>>m;
		vector<edge>e;
		for (int i=0;i<m;i++)
			{
				edge a;
				cin>>a.start>>a.finish>>a.cost;
				a.start--;
				a.finish--;
				e.push_back(a);
			}
		vector<int> length (n, INT_MIN);
		vector<int> p (n, -1);
		length[0] = 0;
		int x;
		for (int i=0;i<n;i++)
			{
				x = -1;
				for (int j=0;j<m;j++)
					if ((length[e[j].start]>INT_MIN)&&(length[e[j].finish]<length[e[j].start] + e[j].cost))
							{
								length[e[j].finish]=length[e[j].start] + e[j].cost;
								p[e[j].finish]=e[j].start;
								x=1;
							}
			}
		vector<int> path;
		int k=0;
		for (int i=n-1;i!=-1;i=p[i])
			{
				k++;
				path.push_back (i);
				if(k>n) break;
			}
		if(length[n-1]==INT_MIN) cout<<":("<<endl;
		else 
			 if((x!=-1)&&((path.back()!=0)||(path.front()!=n-1)||(k>n))) cout<<":)"<<endl;
			 else cout<<length[n-1]<<endl;
		return 0;
	}