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.

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

Author Archives: Yezhkova

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

Задача

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

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

Тесты

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

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

Алгоритм

Оптимизация

Ссылки

Related Images:

e-olymp 1821. Comparing Answers

Problem

Input

Output

Tests

Code

Solution

Links&References

Related Images: