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

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

Задача

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

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

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

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

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

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

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

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

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

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

Тесты

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

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

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

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

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

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

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

#include <iostream>

#include <vector>

using namespace std;

enum color_t {

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

};

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

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

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

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

color[crossroad] = GRAY;

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

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

}

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

return false;

}

int main() {

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

cin >> n >> m;

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

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

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

cin >> u >> v;

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

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

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

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

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

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

}

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

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

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

}

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

}

Объяснение

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

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

Ссылки

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

Related Images:

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

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

Задача

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

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

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

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

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

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

Тесты

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

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

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

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

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

#include <iostream>

#include <vector>

#include <queue>

using namespace std;

int main() {

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

cin >> n >> m >> k;

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

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

{

cin >> winner[i];

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

}

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

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

{

int a, b, t;

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

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

b--;

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

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

}

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

cin >> start;

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

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

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

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

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

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

{

start = plan.front();

plan.pop();

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

{

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

{

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

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

}

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

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

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

{

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

{

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

}

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

}

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

{

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

}

else

{

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

}

return 0;

}

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

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

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

    return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int main() {

int n, m, k;

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

vector<int> winner(m);

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

{

cin >> winner[i];

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

}

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

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

{

int a, b, t;

cin >> a >> b >> t;

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

b--;

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

{

path[a][b] = t;

path[b][a] = t;

}

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

cin >> start;

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

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

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

count[start] = 0;

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

{

int next = -1, mini = 1e6;

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

{

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

{

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

}

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

{

next = j;

mini = count[j];

}

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

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

}

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

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

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

{

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

{

deliver = false;

}

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

}

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

{

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

}

else // Иначе

{

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

}

return 0;

}

Объяснение

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

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

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

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

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

Ссылки

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

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

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

Related Images:

e-olymp 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 88. Месть Ли Чака

04/02/2018 by Кирилл Волков

Задача

“Я хочу быть пиратом!” Мы напоминаем эту известную фразу Гайбраша Трипвуда из серии компьютерных игр Monkey Island («Остров Обезьян»). Гайбраш участвовал в другом приключении и серьезно нуждается в Вашей помощи, потому что на этот раз это вопрос жизни и смерти. Наш Гайбраш в последнем приключении приплыл на таинственный остров (ТО), чтобы найти подсказку для еще более таинственного сокровища. Тем временем Ли Чак узнал об этой поездке и подготовил ловушку Гайбрашу на ТО. ТО имеет прямоугольную форму (поскольку мы знаем, что он таинственный) и его карта может рассматриваться как матрица такой же размерности. Назовем каждый элемент матрицы участком. Некоторые участки могут быть заполнены горными скалами. Такие участки считаются непроходимыми.

Рассмотрим остров, карта которого изображена на рисунке. Эта карта представляет собой матрицу с $6$ строками и $7$ столбцами. Комнаты «R» показывают участки со скалами. Гайбраш должен начинать с участка, отмеченного «g», а Ли Чак – с участка «l». У Гайбраша есть шанс сбежать с этого проклятого острова, если он достигнет конечного участка, который отмечен символом «e» на карте. Каждую единицу времени Гайбраш может пойти на соседний с текущим участок по горизонтали или вертикали (но не по диагонали), если в нем нет скал, или не двигаться. То есть он может переместиться на один участок вверх, вниз, влево, вправо или вообще остаться на месте. В приведенном примере Гайбраш в первый момент времени может остаться или пойти в комнату слева от него. Все указанные правила применяются также и к движению Ли Чака, но с одним исключением: он не может войти на конечный участок (отмеченный «e»). То есть, каждую единицу времени Ли Чак может пойти на один участок вверх, вниз, влево, вправо (если только это не «R» или «e») или стоять. Мы предполагаем, что каждую единицу времени сначала делает ход (или стоит) Гайбраш, а затем ходит (или стоит) Ли Чак, в следующую единицу времени опять сначала Гайбраш, затем Ли Чак и так далее. Если Гайбраш и Ли Чак встретятся на одном участке, то Ли Чак немедленно убьет нашего бедного Гайбраша.

Ваша задача состоит в том, чтобы узнать, есть ли по крайней мере один безопасный путь или нет. Безопасный путь – это путь для Гайбраша (от «g» до «e») такой, что Ли Чак не может поймать Гайбраша на этом пути независимо от того, что он (Ли Чак) делает каждую единицу времени.

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

Первая строка входа содержит единственное целое число — количество тестовых случаев. Далее идут строки данных для тестовых случаев. Каждый тест начинается со строки, содержащей два целых числа $R$ и $C$ ($4 \leq R, C \leq 30$), которые обозначают количество строк и столбцов карты таинственного острова соответственно. Далее следуют $R$ строк, каждая содержит $C$ символов, представляющих карту. Есть единственные отметки «g», «l» и «e» на карте.

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

Для каждого теста необходимо вывести единственную строку. Если существует, по крайней мере, хотя бы один безопасный путь для тестового случая, должно быть выведено слово «YES», и слово «NO», если такого пути нет. Предполагается, что если существует безопасный путь, то необходимо не более $1000$ единиц времени для прохождения по нему Гайбраша.

Тесты

Входные данные	Выходные данные
$531$ $348$ $1645$	$911$
$1784353$ $453345$ $463973$	$214457$
$39252362$ $345673$ $786536$	$302328$
$68790234$ $679643$ $789057$	$281232$
$324$ $8564$ $45074547$	$32984424$

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

#include <iostream>
#include <vector>

using  namespace std;

const int INF = 10000000;
const string GAYBRASH = "GAYBRASH";
const string LICHACK = "LICHACK";

struct node{
    int x;
    int y;
};

vector<node> getChildrenBFS(char ** map, node parent, string hero){
    string bannedChars = "R";
    if(hero == LICHACK) bannedChars.push_back('e');
    vector<node> children;
    node leftChild = {parent.x - 1, parent.y};
    node rightChild = {parent.x + 1, parent.y};
    node downChild = {parent.x, parent.y + 1};
    node upChild = {parent.x, parent.y - 1};
    if(bannedChars.find(map[leftChild.y][leftChild.x]) == string::npos){
        children.push_back(leftChild);
    }
    if(bannedChars.find(map[rightChild.y][rightChild.x]) == string::npos){
        children.push_back(rightChild);
    }
    if(bannedChars.find(map[downChild.y][downChild.x]) == string::npos){
        children.push_back(downChild);
    }
    if(bannedChars.find(map[upChild.y][upChild.x]) == string::npos){
        children.push_back(upChild);
    }
    return children;
}

void dfsSecondPlayer(char ** map, int ** moves, string hero, node currentNode, int move){
    moves[currentNode.y][currentNode.x] = move;
    move++;
    vector<node> children = getChildrenBFS(map, currentNode, hero);
    vector<node> queue;
    for(auto e: children) {
        if (move < moves[e.y][e.x]) {
            dfsSecondPlayer(map, moves, hero, e, move);
        }
    }
}
void dfsFirstPlayer(char ** map, int ** moves, int ** secondPlayer, string hero, node currentNode, int move){
    moves[currentNode.y][currentNode.x] = move;
    move++;
    vector<node> children = getChildrenBFS(map, currentNode, hero);
    vector<node> queue;
    for(auto e: children){
        if(move < moves[e.y][e.x] && move < secondPlayer[e.y][e.x]){
            dfsFirstPlayer(map, moves, secondPlayer, hero, e, move);
        }
    }
}
int main() {
    int tests;
    cin >> tests;
    for(; tests > 0; tests--){
        int m;
        int n;
        cin >> m >> n;
        cin.ignore();
        node g;
        node l;
        node e;
        char **map = new char*[m];
        for(int i = 0; i < m; i++){
            map[i] = new char[n];
        }
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                map[i][j] = cin.get();
                switch(map[i][j]){
                    case 'g':
                        g.x = j;
                        g.y = i;
                        break;
                    case 'l':
                        l.x = j;
                        l.y = i;
                        break;
                    case 'e':
                        e.x = j;
                        e.y = i;
                        break;
                }
            }
            cin.ignore();
        }
        int **liChack = new int*[m];
        for(int i = 0; i < m; i++){
            liChack[i] = new int[n];
        }
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                liChack[i][j] = INF;
            }
        }
        dfsSecondPlayer(map, liChack, LICHACK, l, 0);
        int **gaybrash = new int*[m];
        for(int i = 0; i < m; i++){
            gaybrash[i] = new int[n];
        }
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                gaybrash[i][j] = INF;
            }
        }
        dfsFirstPlayer(map, gaybrash, liChack, GAYBRASH, g, 0);
        bool OK = gaybrash[e.y][e.x] != INF;
        cout << (OK ? "YES" : "NO") << endl;
        for(int i = 0; i < m; i++){
            delete[] map[i];
        }
        delete[] map;
        for(int i = 0; i < m; i++){
            delete[] gaybrash[i];
        }
        delete[] gaybrash;
        for(int i = 0; i < m; i++){
            delete[] liChack[i];
        }
        delete[] liChack;
    }
    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

#include <iostream>

#include <vector>

using namespace std;

const int INF = 10000000;

const string GAYBRASH = "GAYBRASH";

const string LICHACK = "LICHACK";

struct node{

int x;

int y;

};

vector<node> getChildrenBFS(char ** map, node parent, string hero){

string bannedChars = "R";

if(hero == LICHACK) bannedChars.push_back('e');

vector<node> children;

node leftChild = {parent.x - 1, parent.y};

node rightChild = {parent.x + 1, parent.y};

node downChild = {parent.x, parent.y + 1};

node upChild = {parent.x, parent.y - 1};

if(bannedChars.find(map[leftChild.y][leftChild.x]) == string::npos){

children.push_back(leftChild);

}

if(bannedChars.find(map[rightChild.y][rightChild.x]) == string::npos){

children.push_back(rightChild);

}

if(bannedChars.find(map[downChild.y][downChild.x]) == string::npos){

children.push_back(downChild);

}

if(bannedChars.find(map[upChild.y][upChild.x]) == string::npos){

children.push_back(upChild);

}

return children;

}

void dfsSecondPlayer(char ** map, int ** moves, string hero, node currentNode, int move){

moves[currentNode.y][currentNode.x] = move;

move++;

vector<node> children = getChildrenBFS(map, currentNode, hero);

vector<node> queue;

for(auto e: children) {

if (move < moves[e.y][e.x]) {

dfsSecondPlayer(map, moves, hero, e, move);

}

void dfsFirstPlayer(char ** map, int ** moves, int ** secondPlayer, string hero, node currentNode, int move){

moves[currentNode.y][currentNode.x] = move;

move++;

vector<node> children = getChildrenBFS(map, currentNode, hero);

vector<node> queue;

for(auto e: children){

if(move < moves[e.y][e.x] && move < secondPlayer[e.y][e.x]){

dfsFirstPlayer(map, moves, secondPlayer, hero, e, move);

}

int main() {

int tests;

cin >> tests;

for(; tests > 0; tests--){

int m;

int n;

cin >> m >> n;

cin.ignore();

node g;

node l;

node e;

char **map = new char*[m];

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

map[i] = new char[n];

}

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

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

map[i][j] = cin.get();

switch(map[i][j]){

case 'g':

g.x = j;

g.y = i;

break;

case 'l':

l.x = j;

l.y = i;

break;

case 'e':

e.x = j;

e.y = i;

break;

}

cin.ignore();

}

int **liChack = new int*[m];

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

liChack[i] = new int[n];

}

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

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

liChack[i][j] = INF;

}

dfsSecondPlayer(map, liChack, LICHACK, l, 0);

int **gaybrash = new int*[m];

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

gaybrash[i] = new int[n];

}

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

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

gaybrash[i][j] = INF;

}

dfsFirstPlayer(map, gaybrash, liChack, GAYBRASH, g, 0);

bool OK = gaybrash[e.y][e.x] != INF;

cout << (OK ? "YES" : "NO") << endl;

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

delete[] map[i];

}

delete[] map;

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

delete[] gaybrash[i];

}

delete[] gaybrash;

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

delete[] liChack[i];

}

delete[] liChack;

}

return 0;

}

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

Предположим, что существует безопасный для Гайбраша маршрут. Это означает, что Ли Чак не может перехватить его ни в одной точке этого маршрута, то есть, что в любую точку маршрута Гайбраш попадает как минимум на один ход раньше, чем Ли Чак. В противном случае безопасного хода нет.
Представим карту острова в виде неориентированного графа, вершинами которого в случае Гайбраша являются все участки, кроме участков с пометкой «R», а для Ли Чака — все участки, кроме участков с пометками «R» и «e». Две вершины будут соединяться ребром, если они соответствуют участкам, имеющим общую сторону. С помощью поиска в глубину найдем минимальное количество шагов, за которое Ли Чак попадает в каждую клетку, в которую он может попасть. Аналогично реализуем поиск в глубину для Гайбраша с той лишь разницей, что Гайбраш должен миновать те вершины графа, в которые он будет добираться дольше, чем Ли Чак. Если при этом найдется путь, соединяющий вершину, соответствующую начальному местоположению Гайбраша с вершиной, соответствующую цели, то он сможет спастись, в противном случае -нет.

Ссылки

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

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 982. Связность

15/05/2016 by Женя Максимова

Задача. Проверить, является ли заданный неориентированный граф связным, то есть что из любой вершины можно по рёбрам этого графа попасть в любую другую.

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

В первой строке заданы количество вершин [latex]n[/latex] и ребер [latex]m[/latex] в графе соответственно [latex](1 \leq n \leq 100, 1 \leq m \leq 10000)[/latex]. Каждая из следующих m строк содержит по два числа [latex]u_i[/latex] и [latex]v_i[/latex] [latex](1 \leq u_i, v_i \leq n);[/latex] каждая такая строка означает, что в графе существует ребро между вершинами [latex]u_i[/latex] и [latex]v_i[/latex].

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

Выведите «YES», если граф является связным и «NO» в противном случае.

Тесты

Тесты, взятые с e-olymp.com

Test	Input	Output
1	3 2 1 2 3 2	YES
2	3 1 1 3	NO

Мои тесты

Test	Input	Output
1	4 2 1 2 3 4	NO
2	4 5 1 2 2 1 2 4 2 4 4 2	NO
3	5 4 1 2 5 1 3 5 4 3	YES

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

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

#define in_range(x,y,z) for(int x=y; x<z; x++)

int main()
{
  int m,n;
  cin >> n >> m;
  vector < vector<int> > g(n); // граф
  int s=0; // начальная вершина
  in_range(i,0,m) // считывание графа
    {
      int u,v;
      cin >> u >> v;
      g[u-1].push_back(v-1);
      g[v-1].push_back(u-1);
    }
  queue<int> q; // очередь с вершинами, которые мы рассматриваем на данном этапе
  q.push (s);
  vector<bool> used (n); // логический массив, указывающий, посещена ли вершина
  used[s] = true;
  while (!q.empty()) // пока мы не обойдем все вершины, которые можно достигнуть из данной
    {
      int v = q.front();
      q.pop(); // достаем из головы очереди одну вершину
      for (size_t i=0; i<g[v].size(); ++i) //просмотрим все ребра, исходящие из данной вершины
        {
          int to = g[v][i];
          if (!used[to]) // если текущая вершина еще не была посещена
            {
              used[to] = true; //отмечаем, что мы ее посетили
              q.push (to); // помещаем в очередь
            }
        }
    }
  vector<bool>::iterator it;
  it = find (used.begin(), used.end(), false); // проверяем, остались ли еще непосещенные вершины
  if (it == used.end())
    cout << "YES"; // если все вершины посещены, то граф связный
  else
    cout << "NO";
  return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define in_range(x,y,z) for(int x=y; x<z; x++)

int main()

{

int m,n;

cin >> n >> m;

vector < vector<int> > g(n); // граф

int s=0; // начальная вершина

in_range(i,0,m) // считывание графа

{

int u,v;

cin >> u >> v;

g[u-1].push_back(v-1);

g[v-1].push_back(u-1);

}

queue<int> q; // очередь с вершинами, которые мы рассматриваем на данном этапе

q.push (s);

vector<bool> used (n); // логический массив, указывающий, посещена ли вершина

used[s] = true;

while (!q.empty()) // пока мы не обойдем все вершины, которые можно достигнуть из данной

{

int v = q.front();

q.pop(); // достаем из головы очереди одну вершину

for (size_t i=0; i<g[v].size(); ++i) //просмотрим все ребра, исходящие из данной вершины

{

int to = g[v][i];

if (!used[to]) // если текущая вершина еще не была посещена

{

used[to] = true; //отмечаем, что мы ее посетили

q.push (to); // помещаем в очередь

}

vector<bool>::iterator it;

it = find (used.begin(), used.end(), false); // проверяем, остались ли еще непосещенные вершины

if (it == used.end())

cout << "YES"; // если все вершины посещены, то граф связный

else

cout << "NO";

return 0;

}

Алгоритм

Чтобы установить, является ли граф связным, я использовала удобный для этого алгоритм поиска в ширину. Он заключается в следующем: начиная с какой-то вершины, мы поочередно просматриваем все вершины, соседние с ней. Каждую посещенную вершину мы помечаем маркером. Затем повторяем этот процесс для каждой из соседних вершин, и так далее. Поиск будет продолжаться, пока мы не обойдем все вершины, которые можно достигнуть из данной. Если после этого в графе осталась хотя бы одна не помеченная вершина, значит из нее нельзя попасть в помеченные, то есть граф не является связным. При этом неважно, с какой вершины мы будем начинать поиск, ведь нам нужно установить сам факт, связный граф или нет.

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

Засчитанное решение на сайте e-olymp.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-olimp 4856. Кратчайший путь

24/04/2015 by Ілларіонова Марія Валеріївна

Задача e-olimp.com №4856. Ссылка на засчитанное решение.

Дан неориентированный взвешенный граф. Найти кратчайший путь между двумя данными вершинами.

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

Первая строка содержит натуральные числа [latex]n[/latex] и [latex]m[/latex] [latex]\left(n\leq 2000, m\leq 50000 \right)[/latex] — количество вершин и рёбер графа. Вторая строка содержит натуральные числа [latex]s[/latex] и [latex]f[/latex] [latex]\left(1\leq s, f\leq n, s\neq f \right)[/latex] — номера вершин, длину пути между которыми требуется найти. Следующие [latex]m[/latex] строк содержат по три числа [latex]b_{i}[/latex], [latex]e_{i}[/latex] и [latex]w_{i}[/latex]- номера концов [latex]i[/latex]-ого ребра и его вес соответственно [latex]\left(1 \leq b_{i}, e_{i}\leq n, 0\leq w_{i}\leq 100000\right)[/latex].

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

Первая строка должна содержать одно число — длину минимального пути между вершинами [latex]s[/latex] и [latex]f[/latex]. Во второй строке через пробел выведите вершины на кратчайшем пути из [latex]s[/latex] в [latex]f[/latex] в порядке обхода. Если путь из [latex]s[/latex] в [latex]f[/latex] не существует, выведите -1.

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

#include <iostream> 
#include <vector>
#include <set>
#include <utility>
using namespace std;
#define INF 1000000000000
#define MAX 100000

vector <pair <int, long long> > G[MAX];
vector <int> path;
vector <int> ans;
set <pair <long long, int> > q;
long long length[MAX];
int parent[MAX];

int main() {
    ios::sync_with_stdio(false);
    int n, m, a, b;
    cin >> n >> m >> a >> b;
    a--, b--; // начнём отсчёт с 0, для удобства
    for (int i=0; i<m; i++) {
        int from, to, len;
        cin >> from >> to >> len;
        from--, to--;
        G[to].push_back(make_pair(from, len));
        G[from].push_back(make_pair (to, len));
    }
    for (int i=0; i<n; i++) length[i]=INF;
    length[a]=0;
    q.insert (make_pair (length[a], a));
    while (!q.empty()) { // будем выполнять, пока наша очередь не пуста
        int v = q.begin()->second;
        q.erase (q.begin());
        for (int i=0; i<G[v].size(); i++) {
            int to=G[v][i].first, len=G[v][i].second;
            if (length[v]+len<length[to]) { // изначально она бесконечно большая, поэтому сразу меньше, а если будет оказываться больше, то просто не будем менять
                   q.erase (make_pair (length[to], to)); // мы убираем нашу бесконечность или больший путь вместе со следующей вершиной, а вместо них
                   length[to]=length[v]+len; // ставим новую длину
                   parent[to]=v; // и записываем предка
                   q.insert (make_pair (length[to], to));
            }
        }
    }
    if (length[b]==INF) { // если последняя вершина оказалась бесконечностью, значит, мы её не достигли
        cout << "-1"; 
        return 0;
    } 
    cout << length[b] << endl;
    int c=b;
    while (c!=a) {
        ans.push_back(c+1); // так как начинали с 1, то увеличиваем
        c=parent[c];
    }
    ans.push_back(a+1);
    cout << ans[ans.size()-1];
    for(int it = ans.size()-2; it >=0; it--) cout << " " << ans[it];
    cout << endl;
    return 0;   
}

#include <iostream>

#include <vector>

#include <set>

#include <utility>

using namespace std;

#define INF 1000000000000

#define MAX 100000

vector <pair <int, long long> > G[MAX];

vector <int> path;

vector <int> ans;

set <pair <long long, int> > q;

long long length[MAX];

int parent[MAX];

int main() {

ios::sync_with_stdio(false);

int n, m, a, b;

cin >> n >> m >> a >> b;

a--, b--; // начнём отсчёт с 0, для удобства

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

int from, to, len;

cin >> from >> to >> len;

from--, to--;

G[to].push_back(make_pair(from, len));

G[from].push_back(make_pair (to, len));

}

for (int i=0; i<n; i++) length[i]=INF;

length[a]=0;

q.insert (make_pair (length[a], a));

while (!q.empty()) { // будем выполнять, пока наша очередь не пуста

int v = q.begin()->second;

q.erase (q.begin());

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

int to=G[v][i].first, len=G[v][i].second;

if (length[v]+len<length[to]) { // изначально она бесконечно большая, поэтому сразу меньше, а если будет оказываться больше, то просто не будем менять

q.erase (make_pair (length[to], to)); // мы убираем нашу бесконечность или больший путь вместе со следующей вершиной, а вместо них

length[to]=length[v]+len; // ставим новую длину

parent[to]=v; // и записываем предка

q.insert (make_pair (length[to], to));

}

if (length[b]==INF) { // если последняя вершина оказалась бесконечностью, значит, мы её не достигли

cout << "-1";

return 0;

}

cout << length[b] << endl;

int c=b;

while (c!=a) {

ans.push_back(c+1); // так как начинали с 1, то увеличиваем

c=parent[c];

}

ans.push_back(a+1);

cout << ans[ans.size()-1];

for(int it = ans.size()-2; it >=0; it--) cout << " " << ans[it];

cout << endl;

return 0;

}

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