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 2270. Поиск цикла

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

Задача

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

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

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

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

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

Тесты

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

import java.util.*;
public class Main {
    public static int n, m, flag = 0;
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
    public static ArrayList<Integer> used = new ArrayList<Integer>();
    public static ArrayList<Integer> path = new ArrayList<Integer>();
    // поиск в глубину для каждой вершины
    static void dfs(int v) {
        if (flag == 1) return; // если уже нашли цикл, то останавливаемся
        else {
            used.set(v, 1); // посещаем вершину
            path.add(v); // добавляем ее в порядок обхода графа
            for (int i = 0; i < graph.get(v).size(); i++) {
                int to = graph.get(v).get(i); // следующая вершина графа
                if (used.get(to) == 1) { // если мы ее посетили, но не вышли из нее, значит мы нашли цикл
                    path.add(to); // добавляем следующую вершину в порядок обхода графа
                    flag = 1; // ставим индикатор, что мы нашли цикл и останавливаемся
                    return;
                }
                else dfs(to); // если не посетили, то посещаем
                if (flag == 1) return; // если нашли цикл, то останавливаемся
            }
            used.set(v, 2); // если не нашли цикл, то выходим из вершины
            path.remove(path.size() - 1);
        }
    }
    // проверяем вершины на наличие цикла
    static void checkNodes() {
        for (int i = 0; i <= n; i++) {
            if (used.get(i) == 0) { // если не посещали вершину, то посещаем ее
                dfs(i);
                if (flag == 1) return; // если нашли цикл, то останавливаемся
            }
        }
    }
    public static void main (String[] args) {
        Scanner s = new Scanner(System.in);
        // считываем количество вершин и ребер
        n = s.nextInt();
        m = s.nextInt();
        for (int i = 0; i <= n; i++) {
            used.add(0);
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            // считываем ребра и заполняем граф
            int v1 = s.nextInt();
            int v2 = s.nextInt();
            graph.get(v1).add(v2);
        }
        checkNodes(); // проверяем вершины на наличие цикла
        if (flag == 1) { // если цикл найден
            int i = path.size() - 2; // последняя вершина цикла
            int to = path.get(path.size() - 1); // вершина в которой зациклились
            while (path.get(i) != to) { // получаем индекс вершины в которой зациклились
                i--;
            }
            System.out.println("YES");
            while (i < path.size() - 1) {  // выводим сам цикл
                System.out.print(path.get(i) + " ");
                i++;
            }
            System.out.println();
        }
        else
            System.out.print("NO");
    }
}

import java.util.*;

public class Main {

public static int n, m, flag = 0;

public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();

public static ArrayList<Integer> used = new ArrayList<Integer>();

public static ArrayList<Integer> path = new ArrayList<Integer>();

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

static void dfs(int v) {

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

else {

used.set(v, 1); // посещаем вершину

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

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

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

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

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

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

return;

}

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

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

}

used.set(v, 2); // если не нашли цикл, то выходим из вершины

path.remove(path.size() - 1);

}

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

static void checkNodes() {

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

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

dfs(i);

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

}

public static void main (String[] args) {

Scanner s = new Scanner(System.in);

// считываем количество вершин и ребер

n = s.nextInt();

m = s.nextInt();

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

used.add(0);

graph.add(new ArrayList<>());

}

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

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

int v1 = s.nextInt();

int v2 = s.nextInt();

graph.get(v1).add(v2);

}

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

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

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

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

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

i--;

}

System.out.println("YES");

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

System.out.print(path.get(i) + " ");

i++;

}

System.out.println();

}

else

System.out.print("NO");

}

Решение

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

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

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

Ссылки

Условие задачи на 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 4764. Степени вершин

28/12/2018 by Артем Чернобровкин

Задача

Простой неориентированный граф задан матрицей смежности. Найдите степени всех вершин графа.

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

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

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

Выведите [latex]n[/latex] чисел — степени всех вершин.

Тесты

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

Код задачи

import java.util.*;
public class Main
{
  public static void main(String[] args)

  {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    //массив, в котором содержатся степени вершин
    int deg[] = new int[n];
    //Чтение матрицы смежности
    //и если есть ребро, то увеличиваем степень на 1
    for(int i = 0; i < n; i++)
    {
    	for(int j = 0; j < n; j++)

		 {
			int value = in.nextInt();
			if (value == 1)
    		{
    			deg[i]++;
    		}
		 }
    }
    //вывод результата
    for(int i = 0; i < n; i++)
    {
      System.out.println(deg[i]);     
    }
  }
}

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner in = new Scanner(System.in);

int n = in.nextInt();

//массив, в котором содержатся степени вершин

int deg[] = new int[n];

//Чтение матрицы смежности

//и если есть ребро, то увеличиваем степень на 1

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

{

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

{

int value = in.nextInt();

if (value == 1)

{

deg[i]++;

}

//вывод результата

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

{

System.out.println(deg[i]);

}

Решение

В ячейке [latex]deg[i][/latex] будем подсчитывать степень вершины [latex]i[/latex], которая равна количеству единиц в i-ой строки матрицы смежности.
Для неориентированного графа степень вершины — это количество всех инцидентных ей ребер.
Граф [latex]G=(V,U)[/latex] может быть задан матрицей смежности. Это квадратная матрица размерности [latex]n\times n[/latex], где [latex]n=\left |V \right | [/latex]. Матрица смежности неориентированного графа симметрична. Элементы матрицы смежности определяются следующим образом.
1- если [latex]i[/latex]-тая и [latex]j[/latex]-тая вершины графа смежны
0- иначе
[latex] a_{ij}=\left\{\begin{matrix}
1\\
0
\end{matrix}\right.\\[/latex]

Ссылки

Задача на e-olymp

Код задачи на ideone

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 5082. Степени вершин

27/12/2018 by Дима Мороз

Задача

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

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

В первой строчке находится число $N (1 ≤ N ≤ 1000)$. В следующих $N$ строчках находится матрица смежности.

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

Выведите $N$ чисел – степени всех вершин.

Тесты

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

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

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

class Main
{
	static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	static PrintWriter out = new PrintWriter(System.out);
	static int nextInt() throws IOException  {
		in.nextToken();
		return (int)in.nval;
	}
	public static void main (String[] args) throws java.lang.Exception
	{
		int n = nextInt();
		for (int i = 0; i < n; i++) {
			int counter = 0, x;
			for (int j = 0; j < n; j++) {
				x = nextInt();
				if (x > 0) counter += (i == j ? 2 : 1);
			}
			out.print (counter + " ");
			out.flush();
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

static PrintWriter out = new PrintWriter(System.out);

static int nextInt() throws IOException {

in.nextToken();

return (int)in.nval;

}

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

{

int n = nextInt();

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

int counter = 0, x;

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

x = nextInt();

if (x > 0) counter += (i == j ? 2 : 1);

}

out.print (counter + " ");

out.flush();

}

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

Для решении задачи даже не нужно запоминать значения элементов матрицы. Выполняем данные действия $N$ раз, для каждой строки матрицы. Храним ответ в переменной counter , изначально $0$. По очереди считываем все ее элементы и, если текущий элемент равен $1$, то прибавялем степени $2$, если элемент принадлежит главной диагонали (т.к. тогда это петля, а при подсчете степени ребро-петля учитывается дважды), иначе — $2$. Затем выводим результат через пробел.

Ссылки

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

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

27/12/2018 by Валерия Ларикова

Задача

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

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

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

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

Вывести [latex]YES,[/latex] если граф простой неориентированный, и [latex]NO[/latex] в противном случае.

Тесты

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

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

import java.util.*;
import java.lang.*;
import java.io.*;
 
public class Main
{
	public static void main(String[] args)  throws IOException
	{
		Scanner in = new Scanner(System.in);
		int 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();
				if ((i == j) && (a[i][j] == 1)) {
					System.out.print("NO");
					return;
				}
			}
		}
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				if (a[i][j] != a[j][i]) {
					System.out.print("NO");
					return;
				}
			}
		}
		System.out.print("YES");
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

public class Main

{

public static void main(String[] args) throws IOException

{

Scanner in = new Scanner(System.in);

int 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();

if ((i == j) && (a[i][j] == 1)) {

System.out.print("NO");

return;

}

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

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

if (a[i][j] != a[j][i]) {

System.out.print("NO");

return;

}

System.out.print("YES");

}

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

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

Ссылки

Ссылка на e-olymp
Ссылка на ideone

e-olymp 93. Truck driving

27/12/2018 by Саша Рябова

Task

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

Input data

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

Output data

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

Tests

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

Code

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

public class TruckDriving {

    public class Node implements Comparable<Node> {

        Integer first;
        Integer second;

        @Override
        public int compareTo(Node other) {
            if (this.first != other.first) {
                return this.first.compareTo(other.first);
            } else {
                return this.second.compareTo(other.second);
            }
        }
    }

    int distance[] = new int[200];

    public TruckDriving() {

        Scanner sc = new Scanner(System.in);
        int testCaseCount = sc.nextInt();
        for (int i = 0; i < testCaseCount; i++) {
            int cityCount = sc.nextInt();
            ArrayList<Node> coordCity = new ArrayList<Node>(cityCount);
            for (int j = 0; j < cityCount; j++) {
                int coordX = sc.nextInt();
                int coordY = sc.nextInt();
                Node city = new Node();
                city.first = coordX;
                city.second = coordY;
                coordCity.add(city);
            }

            findMinimum(coordCity, cityCount);
            // System.out.println(distance.get(1));
            double res = Math.sqrt(distance[1]);
            System.out.format("%.3f", res);
            System.out.println();
        }

    }

    public void findMinimum(ArrayList<Node> coordCity, int cityCount) {
        //  System.out.println(distance);
        distance[0] = 0;
        for (int i = 1; i < cityCount; i++) {
            distance[i] = Integer.MAX_VALUE;
        }

        PriorityQueue<Node> q = new PriorityQueue<Node>();
        Node zeroPair = new Node();
        zeroPair.first = 0;
        zeroPair.second = 0;

        q.add(zeroPair);
        while (!q.isEmpty()) {
            int num_v = q.peek().second;
            Node cur = coordCity.get(num_v);
            int distv = -q.peek().first;
            q.poll();
            for (int j = 0; j < cityCount; j++) {
                int distan = Math.max(distv, (cur.first - coordCity.get(j).first) * (cur.first - coordCity.get(j).first) + (cur.second - coordCity.get(j).second) * (cur.second - coordCity.get(j).second));
                if (distance[j] > distan) {
                    distance[j] = distan;
                    Node tempPair = new Node();
                    tempPair.first=-distan;
                    tempPair.second=j;
                    q.add(tempPair);
                }
            }

        }
    }

    public static void main(String[] args) {
        TruckDriving tr = new TruckDriving();

    }
}

import java.util.ArrayList;

import java.util.LinkedList;

import java.util.PriorityQueue;

import java.util.Scanner;

public class TruckDriving {

public class Node implements Comparable<Node> {

Integer first;

Integer second;

@Override

public int compareTo(Node other) {

if (this.first != other.first) {

return this.first.compareTo(other.first);

} else {

return this.second.compareTo(other.second);

}

int distance[] = new int[200];

public TruckDriving() {

Scanner sc = new Scanner(System.in);

int testCaseCount = sc.nextInt();

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

int cityCount = sc.nextInt();

ArrayList<Node> coordCity = new ArrayList<Node>(cityCount);

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

int coordX = sc.nextInt();

int coordY = sc.nextInt();

Node city = new Node();

city.first = coordX;

city.second = coordY;

coordCity.add(city);

}

findMinimum(coordCity, cityCount);

// System.out.println(distance.get(1));

double res = Math.sqrt(distance[1]);

System.out.format("%.3f", res);

System.out.println();

}

public void findMinimum(ArrayList<Node> coordCity, int cityCount) {

// System.out.println(distance);

distance[0] = 0;

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

distance[i] = Integer.MAX_VALUE;

}

PriorityQueue<Node> q = new PriorityQueue<Node>();

Node zeroPair = new Node();

zeroPair.first = 0;

zeroPair.second = 0;

q.add(zeroPair);

while (!q.isEmpty()) {

int num_v = q.peek().second;

Node cur = coordCity.get(num_v);

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

q.poll();

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

int distan = Math.max(distv, (cur.first - coordCity.get(j).first) * (cur.first - coordCity.get(j).first) + (cur.second - coordCity.get(j).second) * (cur.second - coordCity.get(j).second));

if (distance[j] > distan) {

distance[j] = distan;

Node tempPair = new Node();

tempPair.first=-distan;

tempPair.second=j;

q.add(tempPair);

}

public static void main(String[] args) {

TruckDriving tr = new TruckDriving();

}

Solution

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

Note: To use Node objects in the PriorityQueue, there should be a way to compare this objects. Thus, it was required to overwrite a method CompareTo so that we could implement interface Comparable

References

The task at e-olymp.com

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

27/12/2018 by Саша Рябова

Условие

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

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

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

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

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

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

Тесты

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

Код решения

import java.util.*;

public class Main {

    static int maxn = 100;
    static int bestCost = Integer.MAX_VALUE;
    static int[][] relations = new int[Main.maxn][Main.maxn];

    public static void mincut(int N) {
        Vector<Vector<Integer>> compressed_vertices = new Vector<Vector<Integer>>();
        for (int i = 0; i < N; i++) {
            compressed_vertices.add(new Vector<Integer>());
            compressed_vertices.get(i).add(i);
        }

        int[] weights;
        weights = new int[N];
        boolean[] exist;
        exist = new boolean[N];
        boolean[] in_A;
        in_A = new boolean[N];
        for (int i = 0; i < N; i++) {
            exist[i] = true;
        }
        for (int ph = 0; ph < N - 1; ++ph) {
            for (int i = 0; i < N; i++) {
                in_A[i] = false;
            }
            for (int i = 0; i < N; i++) {
                weights[i] = 0;
            }
            int prev = 0;
            for (int it = 0; it < N - ph; ++it) {
                int sel = -1;
                for (int i = 0; i < N; ++i) {

                    if ((exist[i] == true) && (in_A[i] == false) && (sel == -1 || weights[i] > weights[sel])) {
                        sel = i;
                    }
                }
                if (it == N - ph - 1) {
                    if (weights[sel] < bestCost) {
                        bestCost = weights[sel];
                    }

                    compressed_vertices.get(prev).addAll(compressed_vertices.get(sel));

                    for (int i = 0; i < N; ++i) {
                        relations[prev][i] = relations[i][prev] += relations[sel][i];
                    }
                    exist[sel] = false;
                } else {

                    in_A[sel] = true;
                    for (int i = 0; i < N; ++i) {
                        weights[i] += relations[sel][i];
                    }
                    prev = sel;
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int M = in.nextInt();
        for (int i = 0; i < M; i++) {
            int U = in.nextInt() - 1;
            int V = in.nextInt() - 1;
            relations[U][V] = 1;
            relations[V][U] = 1;
        }
        mincut(N);
        System.out.print(bestCost);
    }

}

import java.util.*;

public class Main {

static int maxn = 100;

static int bestCost = Integer.MAX_VALUE;

static int[][] relations = new int[Main.maxn][Main.maxn];

public static void mincut(int N) {

Vector<Vector<Integer>> compressed_vertices = new Vector<Vector<Integer>>();

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

compressed_vertices.add(new Vector<Integer>());

compressed_vertices.get(i).add(i);

}

int[] weights;

weights = new int[N];

boolean[] exist;

exist = new boolean[N];

boolean[] in_A;

in_A = new boolean[N];

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

exist[i] = true;

}

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

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

in_A[i] = false;

}

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

weights[i] = 0;

}

int prev = 0;

for (int it = 0; it < N - ph; ++it) {

int sel = -1;

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

if ((exist[i] == true) && (in_A[i] == false) && (sel == -1 || weights[i] > weights[sel])) {

sel = i;

}

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

if (weights[sel] < bestCost) {

bestCost = weights[sel];

}

compressed_vertices.get(prev).addAll(compressed_vertices.get(sel));

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

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

}

exist[sel] = false;

} else {

in_A[sel] = true;

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

weights[i] += relations[sel][i];

}

prev = sel;

}

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int N = in.nextInt();

int M = in.nextInt();

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

int U = in.nextInt() - 1;

int V = in.nextInt() - 1;

relations[U][V] = 1;

relations[V][U] = 1;

}

mincut(N);

System.out.print(bestCost);

}

Решение

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

Ссылки

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

e-olymp 992. Города и дороги

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

Задача

В галактике «Milky Way» на планете «Neptune» есть n городов, некоторые из которых соединены дорогами. Император «Maximus» галактики «Milky Way» решил провести инвентаризацию дорог на планете «Neptune». Но, как оказалось, он не силен в математике, поэтому он просит Вас сосчитать количество дорог.

Вводные данные

В первой строке записано число $n$ $(0 \leq n \leq 100)$. В следующих $n$ строках записано по $n$ чисел, каждое из которых является единичкой или ноликом. Причем, если в позиции $(i, j)$ квадратной матрицы стоит единичка, то $i$-ый и $j$-ый города соединены дорогами, а если нолик, то не соединены.

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

Вывести одно число — количество дорог на планете «Neptune».

Тесты

Входные данные	Выходные данные
$3$ $0$ $1$ $1$ $1$ $0$ $1$ $1$ $1$ $0$	$3$
$3$ $0$ $1$ $0$ $1$ $0$ $0$ $0$ $0$ $0$	$1$
$5$ $0$ $1$ $0$ $1$ $1$ $1$ $0$ $0$ $0$ $0$ $0$ $0$ $0$ $0$ $0$ $1$ $0$ $0$ $0$ $0$ $1$ $0$ $0$ $0$ $0$	$3$

Код программы(использование матрицы смежности)

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int[][] x = new int[n][n];
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				x[i][j] = in.nextInt();
			}
		}
		int roads = 0;
		for(int i = 0; i < n; i++) {
			for(int j = i; j < n; j++) {
				if(x[i][j] == 1) roads++;
			}
		}
		System.out.print(roads);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

Scanner in = new Scanner(System.in);

int n = in.nextInt();

int[][] x = new int[n][n];

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

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

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

}

int roads = 0;

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

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

if(x[i][j] == 1) roads++;

}

System.out.print(roads);

}

Решение задачи(использование матрицы смежности)

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

Код программы(потоковая обработка)

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n=0;
		int i;
		while(in.hasNextInt()) {
			i = in.nextInt();
			if(i == 1) n++;
		}
		System.out.print(n/2);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

Scanner in = new Scanner(System.in);

int n=0;

int i;

while(in.hasNextInt()) {

i = in.nextInt();

if(i == 1) n++;

}

System.out.print(n/2);

}

Решение задачи(потоковая обработка)

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

Ссылки

Условие задачи на e-olymp
Код решения на ideone.com(матрица смежности)
Код решения на ideone.com(потоковая обработка)

Задача

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

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

Тесты

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

Объяснение

Ссылки

Задача

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

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

Тесты

№

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

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

Решение

Ссылки

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

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

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

Тесты

Код

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

Первый этап

Второй этап

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

Подготовка

Первый этап

Второй этап

Задача

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

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

Тесты

Код задачи

Решение

Ссылки

Задача

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

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

Тесты

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

Решение

Ссылки

Задача

Тесты

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

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

Ссылки

Задача

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

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

Тесты

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

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

Ссылки

Task

Input data

Output data

Tests

Code

Solution

References

Условие

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

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

Тесты

Код решения

Решение

Ссылки

Задача

Вводные данные

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

Тесты

Код программы(использование матрицы смежности)

Решение задачи(использование матрицы смежности)

Код программы(потоковая обработка)

Решение задачи(потоковая обработка)

Ссылки