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

06/12/2020 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

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

import java.util.*;
 
enum Color {
    WHITE, GRAY, BLACK; // Вводим тип данных, отвечающий за цвет вершины
}
 
class Main {
    static final List<Color> color = new ArrayList<>(); // Список, в котором указаны цвета всех вершин
    static final List<List<Integer>> crossroads = new ArrayList<>(); // Списки смежности перекрестков
 
    public static void main(String[] args) {
        int n, m; // Количество перекрестков и дорог
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        for (int i = 0; i < n; i++) {
            color.add(Color.WHITE); // Окрашиваем все вершины в белый цвет
        }
        for (int i = 0; i < n; i++) {
            crossroads.add(new LinkedList<Integer>());
        }
        for (int i = 0; i < m; i++) {
            int u, v; // Номер перекрестков, соединенных дорогой
            u = in.nextInt();
            v = in.nextInt();
            u--;v--; // Так как по условию отсчёт начинается с первой вершины, вычитаем 1 для удобства
            boolean isAlreadyRoad = false; // Проверяем, не повторяется ли дорога
            List<Integer> uNeighbours = crossroads.get(u);
            List<Integer> vNeighbours = crossroads.get(v);
            if (!uNeighbours.isEmpty() && !vNeighbours.isEmpty()) {
                if (uNeighbours.contains(v)) isAlreadyRoad = true;
            }
            if (!isAlreadyRoad) { // Проверка на повторение
                uNeighbours.add(v); // Добавляем в список доступных перекрестков перекрестка u перекресток v
                vNeighbours.add(u); // Аналогичные действия для перекрестка v, чтобы учесть возможность двусторонней езды
            }
        }
        System.out.print(isTrack(0, 0) ? "YES" : "NO"); // Запускаем метод, что ищет круговую трассу с первого перекрестка и выводим ответ
    }
 
    public static boolean isTrack(int crossroad, int parent) { // Метод, проверяющий наличие круговой трассы
        if (color.get(crossroad) == Color.GRAY) return true; // Условие существования цикла
        color.set(crossroad, Color.GRAY);
        List<Integer> crossroadNeighbours = crossroads.get(crossroad);
        for (Integer nextCrossroad : crossroadNeighbours) { // Переход в соседние вершины
            if (parent != nextCrossroad && isTrack(nextCrossroad, crossroad)) return true; // Вход в вершину, в которую еще не входили
        }
        color.set(crossroad, Color.BLACK); // Если дальше нет цикла, окрашиваем вершину в черный
        return false;
    }
}

import java.util.*;

enum Color {

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

}

class Main {

static final List<Color> color = new ArrayList<>(); // Список, в котором указаны цвета всех вершин

static final List<List<Integer>> crossroads = new ArrayList<>(); // Списки смежности перекрестков

public static void main(String[] args) {

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

Scanner in = new Scanner(System.in);

n = in.nextInt();

m = in.nextInt();

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

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

}

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

crossroads.add(new LinkedList<Integer>());

}

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

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

u = in.nextInt();

v = in.nextInt();

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

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

List<Integer> uNeighbours = crossroads.get(u);

List<Integer> vNeighbours = crossroads.get(v);

if (!uNeighbours.isEmpty() && !vNeighbours.isEmpty()) {

if (uNeighbours.contains(v)) isAlreadyRoad = true;

}

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

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

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

}

System.out.print(isTrack(0, 0) ? "YES" : "NO"); // Запускаем метод, что ищет круговую трассу с первого перекрестка и выводим ответ

}

public static boolean isTrack(int crossroad, int parent) { // Метод, проверяющий наличие круговой трассы

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

color.set(crossroad, Color.GRAY);

List<Integer> crossroadNeighbours = crossroads.get(crossroad);

for (Integer nextCrossroad : crossroadNeighbours) { // Переход в соседние вершины

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

}

color.set(crossroad, Color.BLACK); // Если дальше нет цикла, окрашиваем вершину в черный

return false;

}

Объяснение

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

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

Ссылки

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

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

03/10/2020 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

Код

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static final int NMAX = 100001;
    static ArrayList<ArrayList<Integer>> tree = new ArrayList<ArrayList<Integer>> (NMAX);
    static ArrayList<Integer> killed = new ArrayList<Integer> (NMAX);
    static ArrayList<Boolean> used = new ArrayList<Boolean> (NMAX);
    static ArrayList<Integer> dist = new ArrayList<Integer> (NMAX);
    static int ans = 0;

    public static void kills(int v, int p)
    {
        if (v == p) kills(tree.get(v).get(0), v);
        if (tree.get(v).size() == 2) for (Integer to : tree.get(v)) if (to != p) kills(to, v);
        if (tree.get(v).size() >= 3) killed.set(v, killed.get(v) + 1);
        return;
    }

    public static void goup(int v, int p)
    {
        if (v == p)
        {
            for (Integer to : tree.get(v)) if (dist.get(to) < dist.get(v)) goup(to, v);
            killed.set(v, 0);
            return;
        }
        if (tree.get(v).size() == 2) for (Integer to : tree.get(v)) if (to != p) goup(to, v);
        if (tree.get(v).size() >= 3)
        {
            killed.set(v, killed.get(v) + 1);
            return;
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        for (int i=0;i<NMAX; i++)
        {
            tree.add(new ArrayList<Integer>());
            dist.add(0);
            used.add(false);
            killed.add(0);
        }
        int n,v;
        n = in.nextInt();
        if (n <= 5) {System.out.print(1); return;} // Частный случай
        tree.get(1).add(0); // Корень тоже должен быть "развилкой"
        ArrayList<Integer> leaves = new ArrayList<Integer> ();
        for (int i = 1; i < n; i++)
        {
            v = in.nextInt();
            tree.get(v).add(i+1);
            tree.get(i+1).add(v); //Заполнение графа в том виде, в котором его дают
        }

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

        LinkedList<Integer> q = new LinkedList<>(); dist.set(1, 0);
        q.offer(1); used.set(1, true);
        while (!q.isEmpty())
        {
            int qv = q.poll();
            used.set(qv, true);
            for (Integer to : tree.get(qv))                //BFS заполняющий вектор dist
            {
                if (!used.get(to))
                {
                    q.offer(to);
                    dist.set(to, dist.get(qv)+1);
                }
            }
        }

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

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

100

101

102

103

104

105

import java.util.ArrayList;

import java.util.LinkedList;

import java.util.Queue;

import java.util.Scanner;

public class Main {

static final int NMAX = 100001;

static ArrayList<ArrayList<Integer>> tree = new ArrayList<ArrayList<Integer>> (NMAX);

static ArrayList<Integer> killed = new ArrayList<Integer> (NMAX);

static ArrayList<Boolean> used = new ArrayList<Boolean> (NMAX);

static ArrayList<Integer> dist = new ArrayList<Integer> (NMAX);

static int ans = 0;

public static void kills(int v, int p)

{

if (v == p) kills(tree.get(v).get(0), v);

if (tree.get(v).size() == 2) for (Integer to : tree.get(v)) if (to != p) kills(to, v);

if (tree.get(v).size() >= 3) killed.set(v, killed.get(v) + 1);

return;

}

public static void goup(int v, int p)

{

if (v == p)

{

for (Integer to : tree.get(v)) if (dist.get(to) < dist.get(v)) goup(to, v);

killed.set(v, 0);

return;

}

if (tree.get(v).size() == 2) for (Integer to : tree.get(v)) if (to != p) goup(to, v);

if (tree.get(v).size() >= 3)

{

killed.set(v, killed.get(v) + 1);

return;

}

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

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

{

tree.add(new ArrayList<Integer>());

dist.add(0);

used.add(false);

killed.add(0);

}

int n,v;

n = in.nextInt();

if (n <= 5) {System.out.print(1); return;} // Частный случай

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

ArrayList<Integer> leaves = new ArrayList<Integer> ();

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

{

v = in.nextInt();

tree.get(v).add(i+1);

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

}

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

{

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

}

LinkedList<Integer> q = new LinkedList<>(); dist.set(1, 0);

q.offer(1); used.set(1, true);

while (!q.isEmpty())

{

int qv = q.poll();

used.set(qv, true);

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

{

if (!used.get(to))

{

q.offer(to);

dist.set(to, dist.get(qv)+1);

}

for (Integer l : leaves)

{

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

}

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

int wentup = 1;

while (wentup != 0)

{

wentup = 0;

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

{

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

{

if (killed.get(i) == 1 && dist.get(i) == l)

{

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

wentup++;

}

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

System.out.print(ans);

}

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

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

Определим для этого $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$ и эти развилки нужно будет тоже закрыть. Для дерева выше, будет закрыт корень.

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

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

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

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

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

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

Подготовка

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

Первый этап

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

Второй этап

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

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

e-olymp 974. Флойд-1

27/12/2018 by Даниель Савчак

Задача

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

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

В первой строке записано количество вершин графа n (1 ≤ n ≤ 100). В следующих n строках записано по n чисел — матрица смежности графа (j-ое число в i-ой строке соответствует весу ребра из вершины i в вершину j). Все числа по модулю не превышают 100. На главной диагонали матрицы — всегда нули.

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

Выведите n строк по n чисел — матрицу кратчайших расстояний между парами вершин. j-ое число в i-ой строке должно равняться весу кратчайшего пути из вершины i в вершину j.

Тесты

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

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

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n;
		n = in.nextInt();
		int [][] a = new int[n][n];
		for( int i=0 ; i<n ; i++ )
    	{
        	for( int j=0 ; j<n ; j++ )
        	{
        	    a[i][j] = in.nextInt();
       		}
    	}
    
    	for( int k=0 ; k<n ; k++ )
    	{
        	for( int i=0 ; i<n ; i++ )
        	{
        	    for( int j=0 ; j<n ; j++ )
        	    {
        	    	if( i!=j )
                	{
                	    a[i][j] = Math.min(a[i][j], a[i][k]+a[k][j]);
              		}
        		}
    		}
		}
		for( int i=0 ; i<n ; i++ )
    	{
    	    for( int j=0 ; j<n ; j++ )
    	    {
    	    	System.out.print(a[i][j]);
    	    	if(j+1 == n)
    	    	{
    	    		System.out.print("\n");
    	    	}
    	    	else {
    	    		System.out.print(' ');
    	    	}
    	    }
		}
	}
}

/* package whatever; // don't place package name! */

import java.util.*;

import java.lang.*;

import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

int n;

n = in.nextInt();

int [][] a = new int[n][n];

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

{

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

{

a[i][j] = in.nextInt();

}

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

{

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

{

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

{

if( i!=j )

{

a[i][j] = Math.min(a[i][j], a[i][k]+a[k][j]);

}

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

{

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

{

System.out.print(a[i][j]);

if(j+1 == n)

{

System.out.print("\n");

}

else {

System.out.print(' ');

}

Решение

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

Ссылки

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

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

e-olymp 977. Дерево?

26/12/2018 by Костя Григорян

Задача

Неориентированный граф без петель и кратных ребер задан матрицей смежности. Определить, является ли этот граф деревом.

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

Первая строка содержит количество вершин графа $n \left (1 \leq n \leq 100 \right).$ Далее записана матрица смежности размером $n × n$, в которой $1$ обозначает наличие ребра, $0$ — его отсутствие. Матрица симметрична относительно главной диагонали.

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

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

Тесты

Входные данные	Выходные данные
[latex]3 \\ 0 \ 1 \ 0 \\ 1 \ 0 \ 1 \\ 0 \ 1 \ 0[/latex]	[latex]YES[/latex]
[latex]2 \\ 0 \ 1 \\ 1 \ 0[/latex]	[latex]YES[/latex]
[latex]4 \\ 0 \ 0 \ 0 \ 1 \\ 0 \ 0 \ 1 \ 0 \\ 0 \ 1 \ 0 \ 0 \\ 1 \ 0 \ 0 \ 0[/latex]	[latex]NO[/latex]
[latex]1 \\ 0[/latex]	[latex]YES[/latex]

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

import java.util.Scanner;
import java.util.ArrayList;

class Main
{
	private static void dfs(int v, int p, ArrayList<ArrayList<Integer>> g , int[] A) {
		A[v]++;
		if (A[v]>1)
			return;
		for (int i=0; i<g.get(v).size(); i++)
		{
			if (g.get(v).get(i)!=p)
				dfs(g.get(v).get(i), v, g, A);
		}
	}
	
	public static void main (String[] args)
	{
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int[] A = new int[n];
		ArrayList<ArrayList<Integer>> g = new ArrayList<ArrayList<Integer>>();
		for (int i=0; i<n; i++) {
			ArrayList<Integer> r = new ArrayList<Integer>();
			for (int j=0; j<n; j++) {
				int a = scanner.nextInt();
				if (a==1) {
					r.add(j);
				}
			}
			g.add(r);
		}
		int t=0;
		dfs(0, -1, g, A);
		for (int i=0; i<n; i++)
		{
			if (A[i]!=1)
			{
				t++;
				break;
			}
		}
		if (t!=0)
			System.out.print("NO");
		else
			System.out.print("YES");
	}
}

import java.util.Scanner;

import java.util.ArrayList;

class Main

{

private static void dfs(int v, int p, ArrayList<ArrayList<Integer>> g , int[] A) {

A[v]++;

if (A[v]>1)

return;

for (int i=0; i<g.get(v).size(); i++)

{

if (g.get(v).get(i)!=p)

dfs(g.get(v).get(i), v, g, A);

}

public static void main (String[] args)

{

Scanner scanner = new Scanner(System.in);

int n = scanner.nextInt();

int[] A = new int[n];

ArrayList<ArrayList<Integer>> g = new ArrayList<ArrayList<Integer>>();

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

ArrayList<Integer> r = new ArrayList<Integer>();

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

int a = scanner.nextInt();

if (a==1) {

r.add(j);

}

g.add(r);

}

int t=0;

dfs(0, -1, g, A);

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

{

if (A[i]!=1)

{

t++;

break;

}

if (t!=0)

System.out.print("NO");

else

System.out.print("YES");

}

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

Считываем граф в ArrayList<ArrayList>. Далее выбираем любую вершину и запускаем из нее своего рода dfs. Заключается он в том, что мы идем к потомкам текущей вершины, попутно смотря были ли мы здесь. Если были, завершаем процесс, так как мы нашли цикл (граф, содержащий цикл, не является деревом). При этом мы не идем от потомка к предку. В конце проверяем обошли ли мы все вершины и не встречались ли нам циклы.

Ссылки

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

e-olymp 1388. Заправки

16/12/2017 by Эммануил Прокопов

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

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

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

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

Сначала идет количество городов n (1 ≤ n ≤ 100), затем идет n чисел, i-ое из которых задает стоимость бензина в i-ом городе (все числа целые из диапазона от 0 до 100). Затем идет количество дорог m в стране, далее идет описание самих дорог. Каждая дорога задается двумя числами — номерами городов, которые она соединяет. Все дороги двухсторонние (то есть по ним можно ездить как в одну, так и в другую сторону); между двумя городами всегда существует не более одной дороги; не существует дорог, ведущих из города в себя.

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

Выведите одно число — суммарную стоимость маршрута или -1, если добраться невозможно.

Тесты

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

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

import java.util.*;

class Main
{
	//Условная бесконечность
	public static final int INF = 1000000;
	
	public static void main (String[] args)
	{
		Scanner input = new Scanner(System.in);
		int n, m, curFrom, curTo;
		n = input.nextInt();
		
		int price[] = new int[n+1];     //Цены на бензин в i-ом городе
		int distance[] = new int[n+1];  //Минимальные затраты на то, чтобы обраться до i-го города
		boolean used[] = new boolean[n+1]; //Был ли рассмотрен этот город?
		Vector <Integer> graph[] = new Vector[n+1];
		for (int i = 1; i <= n; ++i) {
			price[i] = input.nextInt();
			distance[i] = INF;
			used[i] = false;
			graph[i] = new Vector();
		}
		//Заполнение списка смежности
		m = input.nextInt();
		for (int i = 0; i < m; ++i) {
			curFrom = input.nextInt();
			curTo = input.nextInt();
			graph[curFrom].add(curTo);
			graph[curTo].add(curFrom);
		}
		//Нахождение оптимальной стоимости маршрута. На каждой итерации цикла находим город,
		//стоимость маршрута из начального города к которому минимальна. Если оказывается,
		//что эта стоимость бесконечна, значит, искомого пути не существует.
		distance[1] = 0;
		for(int i = 0; i < n; ++i) {
			int curCity = -1; //Город, рассматривыемый в данной итерации
			for (int j = 1; j <= n; ++j)
				if (!used[j] && (curCity == -1 || distance[j] < distance[curCity])) curCity = j;
			if (distance[curCity] == INF) break;
			used[curCity] = true;
			//Релаксация стоимости маршрута для всех городов, в которые можно попасти из данного
			for(int j = 0; j < graph[curCity].size(); ++j) {
				int to = graph[curCity].elementAt(j); 
				distance[to] = Math.min(distance[to], distance[curCity] + price[curCity]);
			}
		}
		//Вывод ответа
		System.out.print(distance[n] == INF ? -1 : distance[n]);
	}
}

import java.util.*;

class Main

{

//Условная бесконечность

public static final int INF = 1000000;

public static void main (String[] args)

{

Scanner input = new Scanner(System.in);

int n, m, curFrom, curTo;

n = input.nextInt();

int price[] = new int[n+1]; //Цены на бензин в i-ом городе

int distance[] = new int[n+1]; //Минимальные затраты на то, чтобы обраться до i-го города

boolean used[] = new boolean[n+1]; //Был ли рассмотрен этот город?

Vector <Integer> graph[] = new Vector[n+1];

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

price[i] = input.nextInt();

distance[i] = INF;

used[i] = false;

graph[i] = new Vector();

}

//Заполнение списка смежности

m = input.nextInt();

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

curFrom = input.nextInt();

curTo = input.nextInt();

graph[curFrom].add(curTo);

graph[curTo].add(curFrom);

}

//Нахождение оптимальной стоимости маршрута. На каждой итерации цикла находим город,

//стоимость маршрута из начального города к которому минимальна. Если оказывается,

//что эта стоимость бесконечна, значит, искомого пути не существует.

distance[1] = 0;

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

int curCity = -1; //Город, рассматривыемый в данной итерации

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

if (!used[j] && (curCity == -1 || distance[j] < distance[curCity])) curCity = j;

if (distance[curCity] == INF) break;

used[curCity] = true;

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

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

int to = graph[curCity].elementAt(j);

distance[to] = Math.min(distance[to], distance[curCity] + price[curCity]);

}

//Вывод ответа

System.out.print(distance[n] == INF ? -1 : distance[n]);

}

Описание

Оптимальную стоимость маршрута будем находить по алгоритму Дейкстры. Цены на бензин в i-ом городе хранятся в массиве price. Минимальные стоимости маршрутов к каждому из городов хранятся в массиве distance, изначально все маршруты принимаем бесконечно дорогими. Кроме того, для хранения информации о том, был ли рассмотрен i-й город, используется массив used. Сам граф представляется в виде списка смежности. Для этого используется массив векторов <strong>graph</strong>. Если в итоге стоимость маршрута до целевого города осталась бесконечной, значит, пути к нему не существует, и выводится -1. Иначе выводится эта стоимость.

Код на ideone.com.

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

e-olymp 5072. Подсчет количества ребер

06/07/2017 by Присяжный Михаил

Постановка задачи

Ссылка на задачу с сайта e-olymp

Ориентированный граф задан матрицей смежности. Найдите количество ребер в графе.

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

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

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

Выведите в выходной файл количество ребер заданного графа.

Тест

№	Значения	Результат
1	3 0 1 1 1 0 1 0 1 1	6

Решение

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	public static void main (String[] args)
	{
		int n;
    	Scanner sc =new Scanner(System.in);
    	n=sc.nextInt();
 		int k, l=0;
    	for(int i=0;i<n;i++){
        	for(int j=0; j<n; j++){
            	k=sc.nextInt();
            	if (k>0)
            	l++;
    		}
    	}
 		System.out.println(l);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args)

{

int n;

Scanner sc =new Scanner(System.in);

n=sc.nextInt();

int k, l=0;

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

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

k=sc.nextInt();

if (k>0)

l++;

}

System.out.println(l);

}

Ссылка на решение задания с сайта e-olymp

Ссылка на решение задания на онлайн компиляторе Ideone.com

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

Объявляем переменную n типа int. Чтобы найти количество ребер в графе, вводим в двух циклах каждый элемент матрицы смежности и если значение больше нуля, то увеличиваем сумму.

e-olymp 975. Флойд

04/07/2017 by Шостак Дмитрий

Задача

Постановка задачи на e-olymp.

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

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

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

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

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

Тесты

№	n	matrix	Результат
1	4	0 5 9 -1 -1 0 2 8 -1 -1 0 7 4 -1 -1 0	16
2	3	0 -1 2 2 0 -1 4 1 0	4
3	5	0 -1 -1 3 4 2 0 3 -1 4 -1 4 0 -1 4 3 -1 2 0 1 1 1 -1 -1 0	8

Ссылка на успешно пройденные тесты на сайте e-olymp.

Решение

import java.util.*;
public class Graph {

    public static void main(String[] args){
        Scanner input =  new Scanner(System.in);

        int n, max = 0;
        n = input.nextInt();
        int[][] matrix = new int[n][n];

        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                matrix[i][j] = input.nextInt();
            }
        }

        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                for(int k = 0; k < n; k++){
                    if(j != k && matrix[j][i] != -1 && matrix[i][k] != -1){
                        if(matrix[j][k] == -1)
                            matrix[j][k] = matrix[j][i] + matrix[i][k];
                        else
                            matrix[j][k] = Math.min(matrix[j][k], matrix[j][i] + matrix[i][k]);
                    }
                }
            }
        }

        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(matrix[i][j] > max) max = matrix[i][j];
            }
        }

        System.out.println(max);
    }
}

import java.util.*;

public class Graph {

public static void main(String[] args){

Scanner input = new Scanner(System.in);

int n, max = 0;

n = input.nextInt();

int[][] matrix = new int[n][n];

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

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

matrix[i][j] = input.nextInt();

}

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

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

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

if(j != k && matrix[j][i] != -1 && matrix[i][k] != -1){

if(matrix[j][k] == -1)

matrix[j][k] = matrix[j][i] + matrix[i][k];

else

matrix[j][k] = Math.min(matrix[j][k], matrix[j][i] + matrix[i][k]);

}

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

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

if(matrix[i][j] > max) max = matrix[i][j];

}

System.out.println(max);

}

Проверить работу кода можно в облаке по ссылке — Ideone.

Пояснения

Данная задача решается при использовании алгоритма Флойда-Уоршелла, суть которого состоит в нахождении длин кратчайших путей между всеми парами вершин во взвешенном ориентированном графе. Код данного алгоритма можно наблюдать в цикле по [latex]i[/latex], в котором имеются два вложенных цикла по [latex]j[/latex] и по [latex]k[/latex]. Здесь мы проходим по элементам матрицы смежности графа, проверяя существует ли ребро между вершинами. Далее следуя алгоритму Флойда выполняем следующее действие — с помощью функции Math.min() находим минимальный путь из одной вершины в другую, записывая его в матрицу. По нахождении всех кратчайших путей, находим максимальный из них, и выводим его в консоль.