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 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
Код решения

Binary Heap (двоичная куча)

22/12/2015 by marchelaphil

В данном отчёте я напишу о структуре данных под названием куча (Heap), а точнее — о её разновидности.

Двоичная куча

Двоичная куча — структура данных, двоичное дерево, для которого выполнены три условия:

Значение в любой вершине не меньше чем значение в потомках
Расстояние до корня отличается не более чем на один уровень
Заполняется слева на право

Зафиксируем операции, которые будем проводить над кучей:

Достать максимальный элемент из кучи, не удаляя его
Добавить элемент в кучу
Создать кучу
Отсортировать массив путём превращения его в кучу, а кучи — в отсортированный массив
Узнать размер кучи
Удалить максимальный элемент из кучи

Описание методов

1. Восстановление свойства кучи

Каждый элемент помещается в конец кучи, потом становится на своё место, соответственно свойств кучи.

Сложность: [latex]O(\log(n))[/latex]

2. Возврат максимального элемента

Возвратить содержимое самой верхней вершины.

Сложность: [latex]O(1)[/latex]

3. Удаление максимального элемента

Меняются местами первая и последняя вершины, после чего последняя вершина запоминается и удаляется, а новая первая вершина проталкивается в кучу, согласно её свойствам.

Сложность: [latex]O(\log(n))[/latex]

4. Пирамидальная сортировка

Достаточно заметить, что в самую первую вершину кучи всегда (по крайней мере, по введённым свойствам) встаёт максимальный элемент. Если каждый раз удалять максимальный элемент — получим отсортированный массив.

Сложность: [latex]O(n\log(n))[/latex]

О реализации

Реализуется структура данных с абстрактным типом данных. Для хранения вершин будем использовать ArrayList. Для каждой вершины под номером [latex]i[/latex] её левый сын хранится в [latex]2*i+1[/latex] вершине, а правый — в [latex]2*i+2[/latex] вершине.

Класс содержит следующие методы:

Heap() — конструктор
shiftUp() — восходящее восстановление свойства кучи
shiftDown() — нисходящее восстановление свойства кучи
insert() — добавление элемента в кучу
delete() — удаление первой вершины
size() — размер кучи
isEmpty() — проверка на пустоту
toString() — преобразование в строку
max() — максимальный элемент
print() — вывод кучи на экран

Код

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Heap <T extends Comparable<T> > {
    //arraylist is much better than an array. There is no need to carry about a capacity.
    private ArrayList<T> items;
 
    //construct
    public Heap() {
        items = new ArrayList<T> ();   
    }
 
    //using shiftUp for insert. 
    private void shiftUp () {
        int k = items.size() - 1;
        while (k > 0){
            int curr = (k-1)/2;
            T Item = items.get(k);
            T Parent = items.get(curr);
            if (Item.compareTo(Parent) > 0){
                items.set(k, Parent);
                items.set(curr, Item);
                k = curr;
            }
            else break;
        }
    }
 
    //using shiftDown fo delete
    private void shiftDown() {
        int curr = 0; 
        int leftChild = 2*curr+1;
        while (leftChild < items.size()) {
            int max = leftChild;
            int rightChild = leftChild + 1;
            if (rightChild < items.size()) {
                if (items.get(rightChild).compareTo(items.get(1)) > 0) {
                    ++max;
                }
            }
            if (items.get(curr).compareTo(items.get(max)) < 0) {
                T tmp = items.get(curr);
                items.set(curr, items.get(max));
                items.set(max, tmp);
                curr = max;
                leftChild = 2*curr+1;
            }
            else break;
        }
    }
 
    public void insert(T item) {
        items.add(item);
        shiftUp();
    }
 
    public T delete() throws NoSuchElementException {
        if (items.size() == 0) {
            throw new NoSuchElementException();
        }
        if (items.size() == 1) return items.remove(0);
        T x = items.get(0);
        items.set(0, items.remove(items.size()-1));
        shiftDown();
        return x;
    }
 
    public int size() {
        return items.size();
    }
 
    public boolean isEmpty() {
        return items.isEmpty();
    }
 
    public String toString() {
        return items.toString();
    }
 
    public T max() {
        return items.get(0);
    }
    public void print() {
        for (int i = 0; i < items.size(); i++) {
            System.out.print(items.get(i).toString() + " ");
        }
        System.out.println();
    }
}
 
class Codechef {   
	public static void main (String[] args) {
		Heap <Integer> test = new Heap<Integer> ();
		test.insert(16);
		test.insert(9);
		test.insert(11);
		test.insert(10);
		test.insert(13);
		test.insert(31);
		test.insert(19);
		test.insert(2);
		test.insert(50);
		test.insert(23);
		test.print();
		//To kill some hares in the same time:
		//- isEmpty() works;
		// max() and toString() too
		// so does delete() => shiftDown() works;
		// heapsort :D
		for (;!test.isEmpty();) {
		    System.out.print(test.max().toString() + " ");
		    test.delete();
		}
	}
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

import java.util.*;

import java.lang.*;

import java.io.*;

class Heap <T extends Comparable<T> > {

//arraylist is much better than an array. There is no need to carry about a capacity.

private ArrayList<T> items;

//construct

public Heap() {

items = new ArrayList<T> ();

}

//using shiftUp for insert.

private void shiftUp () {

int k = items.size() - 1;

while (k > 0){

int curr = (k-1)/2;

T Item = items.get(k);

T Parent = items.get(curr);

if (Item.compareTo(Parent) > 0){

items.set(k, Parent);

items.set(curr, Item);

k = curr;

}

else break;

}

//using shiftDown fo delete

private void shiftDown() {

int curr = 0;

int leftChild = 2*curr+1;

while (leftChild < items.size()) {

int max = leftChild;

int rightChild = leftChild + 1;

if (rightChild < items.size()) {

if (items.get(rightChild).compareTo(items.get(1)) > 0) {

++max;

}

if (items.get(curr).compareTo(items.get(max)) < 0) {

T tmp = items.get(curr);

items.set(curr, items.get(max));

items.set(max, tmp);

curr = max;

leftChild = 2*curr+1;

}

else break;

}

public void insert(T item) {

items.add(item);

shiftUp();

}

public T delete() throws NoSuchElementException {

if (items.size() == 0) {

throw new NoSuchElementException();

}

if (items.size() == 1) return items.remove(0);

T x = items.get(0);

items.set(0, items.remove(items.size()-1));

shiftDown();

return x;

}

public int size() {

return items.size();

}

public boolean isEmpty() {

return items.isEmpty();

}

public String toString() {

return items.toString();

}

public T max() {

return items.get(0);

}

public void print() {

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

System.out.print(items.get(i).toString() + " ");

}

System.out.println();

}

class Codechef {

public static void main (String[] args) {

Heap <Integer> test = new Heap<Integer> ();

test.insert(16);

test.insert(9);

test.insert(11);

test.insert(10);

test.insert(13);

test.insert(31);

test.insert(19);

test.insert(2);

test.insert(50);

test.insert(23);

test.print();

//To kill some hares in the same time:

//- isEmpty() works;

// max() and toString() too

// so does delete() => shiftDown() works;

// heapsort :D

for (;!test.isEmpty();) {

System.out.print(test.max().toString() + " ");

test.delete();

}

java@Cat

Учебные материалы по изучению основ языка програvмирования Java

Tag Archives: Дерево

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

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

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

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

Тесты

Код

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

Первый этап

Второй этап

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

Подготовка

Первый этап

Второй этап

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

Задача

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

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

Тесты

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

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

Ссылки

Binary Heap (двоичная куча)

Двоичная куча

Описание методов

О реализации

Код