Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 07.01.2024, 01:54   #1
mlgdanya
Новичок
Джуниор
 
Регистрация: 07.01.2024
Сообщений: 1
По умолчанию Препод сказал показать решение этой задачи до вторника, а я вообще даже не представляю как оно должно выглядеть...Помогите пожалуйста!!!

Каждой твари по паре
Коллекционировать животных можно не только на Ноевом ковчеге, но и на дереве. А дерево, как известно из теории графов, является связным ациклическим графом. Иными словами, дерево состоит из n вершин и n-1 ребра между ними. Каждое ребро соединяет некоторые две вершины дерева. Из любой вершины дерева можно добраться по ребрам до любой другой. Также дерево не содержит циклов, т. е. нельзя построить путь по ребрам из некоторой вершины и вернуться в нее, не пройдя по одному и тому же ребру дважды.
Для расположения животных на нашем дереве сделано q гнезд, где q - четное число. Животным каждого вида предназначены два гнезда.
После расселения по дереву каждая пара одного вида может перемещаться по ребрам дерева между своими гнездами. Они не должны мешать другим видам, т. е. чтобы никакие два пути не имели общего ребра. При этом допускается пересечение путей в вершине. Вам необходимо разместить q/2 видов животных по гнездам таким образом, чтобы пути
животных одного вида удовлетворяли этому условию.(Желательно решать на Python/C++/PascalABC.NET/Java/C#/Rust)


Формат входных данных
В первой строке входных данных находится два целых числа n и q (2≤ n ≤ 2 • 10^5, 2≤n, q четно) — общее количество вершин в дереве и количество вершин, в которых расположены гнезда.
Во второй строке входных данных находятся q различных целых чисел m(i) (1≤ m(i) ≤ n) - номера вершин с гнездами.
В каждой из следующих n - 1 строк входных данных находится два целых u(i) и v(i) ( 1≤ v(i), v(i) ≤ n, u(i)≠v(i) ). Это означает, что между вершинами u(i) и v(i) в дереве проведено ребро.
Гарантируется, что ребра во входных данных образуют дерево.

Формат выходных данных
Выходные данные должны содержать q/2 строк.
В каждой строке должно содержаться два целых числа х(i) и у(i) (1 ≤ x(i), y(i)≤ n) - номера вершин, в которых будут располагаться гнезда i-го вида животных.
Все числа в выходных данных должны быть различны и должны представлять собой номера вершин с гнёздами.
Если разместить животных требуемым образом невозможно, выведите число -1.
Критерии оценивания:
Баллы начисляются за каждый тест в отдельности, но ряд тестов имеют специфическую структуру:
1. u(i) = i, v(i) = i+1
2. u(i) = 1, v(i) = i+1
3. n ≤ 3000, q≤6
4. q=n.
5. Нет дополнительных ограничений.

Ввод:
9 6
1 3 2 5 8 6
3 1
3 2
3 4
3 5
3 6
4 7
7 8
1 9
Вывод:
3 2
8 5
1 6

Последний раз редактировалось mlgdanya; 07.01.2024 в 19:15.
mlgdanya вне форума Ответить с цитированием
Старый 07.01.2024, 15:25   #2
BDA
МегаМодератор
СуперМодератор
 
Аватар для BDA
 
Регистрация: 09.11.2010
Сообщений: 7,356
По умолчанию

Если вообще ничего не представляете как делать по задаче, то лучше сразу создавайте тему во фрилансе с указанием языка программирования, сроков и вознаграждения.
При первом взгляде ничего лучше рекурсивного переборного алгоритма не приходит в голову. Начать перебирать все пути от первого гнезда до остальных. При выборе пути исключать ребра пути из дерева. Брать следующее оставшееся гнездо и перебирать пути из него. Если удалось выбрать пути между всеми гнездами, то печатать список. Если на текущем шаге не удалось найти путь ни в одно из гнезд, то возвращаться на шаг назад и выбирать другой путь для предыдущего гнезда. Но такой алгоритм для больших деревьев явно будет работать слишком долго.
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
BDA вне форума Ответить с цитированием
Старый 07.01.2024, 17:42   #3
ViktorR
Старожил
 
Регистрация: 23.10.2010
Сообщений: 2,338
По умолчанию

Можно пойти и таким путём:
1. Выбрать корневой узел. Поскольку через корневой узел можно перебираться на другие ветви, то претендентом на корневой узел будет узел, от которого идёт максимум ветвей.
2. Просматриваем каждую ветвь на предмет наличия гнёзд.
3. Если число гнёзд на ветви чётное, то соседние пары отдаём под особь.
4. Если число гнёзд нечётное, то дальние от корня соседние пары отдаём под особь, а ближайшее к корню связываем с гнездом на ветви, где гнёзд нечётное число. Проход между такими гнёздами - через корень.

Как вариант, распределяем гнёзда по ветвям с числом гнёзд большим чем одно. Если число гнёзд нечётное, то оставляем свободными ближайшие к корню.
На следующем шаге распределяем особи по свободным гнёздам, которые будут соединяться через корень.

PS:
Цитата:
Баллы начисляются за каждый тест в отдельности, но ряд тестов имеют специфическую структуру:
1. u(i) = i, v(i) = i+1
2. u(i) = 1, v(i) = i+1
3. n ≤ 3000, q≤6
4. q=n.
5. Нет дополнительных ограничений.
Эта часть мне непонятна.

PSS: И да, если решение будет найдено, то не плохо бы его тут оставить.
Как-то так, ...
ViktorR вне форума Ответить с цитированием
Старый 07.01.2024, 18:15   #4
BDA
МегаМодератор
СуперМодератор
 
Аватар для BDA
 
Регистрация: 09.11.2010
Сообщений: 7,356
По умолчанию

Цитата:
Сообщение от ViktorR Посмотреть сообщение
Эта часть мне непонятна.
Это подсказки, какие тесты сделать для проверки решения.
1. u(i) = i, v(i) = i+1 - все вершины дерева на одной "линии" (например, 1-2-3-4-5);
2. u(i) = 1, v(i) = i+1 - все вершины дерева кроме первой связаны с первой (дерево в виде "звезды");
3. n ≤ 3000, q≤6 - много вершин, мало гнезд;
4. q=n - все вершины дерева являются гнездами.
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
BDA вне форума Ответить с цитированием
Старый 07.01.2024, 18:49   #5
ViktorR
Старожил
 
Регистрация: 23.10.2010
Сообщений: 2,338
По умолчанию

Спасибо.
Так понимаю что вершины - это узлы?
У меня сложно с терминологией. Так знаю, что у графа может быть корень, узлы и рёбра.
Слово "вершина" у меня ассоциируется с горами (тут живу).
Как-то так, ...
ViktorR вне форума Ответить с цитированием
Старый 07.01.2024, 21:23   #6
BDA
МегаМодератор
СуперМодератор
 
Аватар для BDA
 
Регистрация: 09.11.2010
Сообщений: 7,356
По умолчанию

Да, узлы, вершины, точки - синонимы в данном случае.
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
BDA вне форума Ответить с цитированием
Старый 10.01.2024, 00:32   #7
ViktorR
Старожил
 
Регистрация: 23.10.2010
Сообщений: 2,338
По умолчанию

Это на Python (условия на язык нет).
Немного повозился в Сети и составил скрипт, который строит дерево с узлами, помеченными как гнездо и выбирает корневой узел.
Код:
class Node():
    def __init__(self, data=None, nest=None):
        self.data = data   # Ключ узла - номер узла
        if nest == '+':    # Так сделано только для визуализации
            self.nest = nest  # '+' - узел-гнездо (или 0 - ноль)
                              # m - вид животного
        else:
            self.nest = ''    # не гнездо (или оставить None)
        self.children = [] # список узлов-соседей
    
    def set_animal(self, animal):
        self.nest = animal
    
    def __repr__(self, indent=""): # Для печати дерева
        return (indent + repr(self.data) + str(self.nest) + "\n"
                + "".join(child.__repr__(indent+"    ")
                          for child in self.children))

def create_tree(edges, nests):
    # Получить набор уникальных ключей
    node_keys = set(key for keys in edges for key in keys)
    
    # Создать словарь с экземплярами узлов для каждого ключа:
    nodes = {}
    for key in node_keys:
        nodes[key] = Node(key,'+') if key in nests else Node(key)

    # Заполнить дочерние атрибуты из edges - установить связи
    # Из списка ребер получаем номер родителя и номер дочернего узла
    for parent, child in edges:
        # Заполняем список узлов-соседей
        nodes[parent].children.append(nodes[child])
        # Удалить дочерние узлы из множества узлов
        # У нас останется только корневой элемент
        node_keys.remove(child)
    # Получить корень из набора, который на данный момент должен содержать только один элемент
    for root_key in node_keys:
        return nodes[root_key]


# Исходные данные
nests = [1, 3, 2, 5, 8, 6]       # Узлы-гнезда
edges = [[3,1],[3,2],[3,4],[3,5],[3,6],[4,7],[7,8],[1,9]] # Список ребер
root = create_tree(edges, nests) # Дерево

print(root)
В результате получается такое дерево (по исходным данным):
Код:
3+
    1+
        9
    2+
    4
        7
            8+
    5+
    6+
Далее можно размещать, но хочется и поспать ...

PS: Первичный код найден тут:
https://stackoverflow.com/questions/...tree-in-python
Как-то так, ...
ViktorR вне форума Ответить с цитированием
Старый 10.01.2024, 08:51   #8
Valick
Форумчанин
 
Регистрация: 27.04.2022
Сообщений: 495
По умолчанию

Уже среда, расходимся
Valick вне форума Ответить с цитированием
Старый 10.01.2024, 15:21   #9
BDA
МегаМодератор
СуперМодератор
 
Аватар для BDA
 
Регистрация: 09.11.2010
Сообщений: 7,356
По умолчанию

Вот код для алгоритма из 2 сообщения:
Код:
from collections import defaultdict

def connect_nests_recursive(nests_set, edges_dict, res_list):
    nest = nests_set.pop()
    checked_nests = set()
    wave = edges_dict[nest]
    backtrace = {node: nest for node in wave}

    while len(wave) > 0:
        for another_nest in wave.intersection(nests_set):
            # exclude another_nest
            nests_set.remove(another_nest)

            if len(nests_set) == 0:
                res_list.append([nest, another_nest])
                return True

            # exclude path edges between nest and another_nest
            node = another_nest
            while node != nest:
                next_node = backtrace[node]
                edges_dict[node].remove(next_node)
                edges_dict[next_node].remove(node)
                node = next_node

            if connect_nests_recursive(nests_set, edges_dict, res_list):
                res_list.append([nest, another_nest])
                return True

            # include another_nest
            nests_set.add(another_nest)
            # include path edges between nest and another_nest
            node = another_nest
            while node != nest:
                next_node = backtrace[node]
                edges_dict[node].add(next_node)
                edges_dict[next_node].add(node)
                node = next_node

            checked_nests.add(another_nest)
        
        if checked_nests == nests_set:
            nests_set.add(nest)
            return False

        next_wave = set()
        for node in wave:
            for next_node in edges_dict[node].difference(set([backtrace[node]])):
                next_wave.add(next_node)
                backtrace[next_node] = node
        wave = next_wave

    nests_set.add(nest)
    return False

def connect_nests(nests, edges):
    nests_set = set(nests)

    edges_dict = defaultdict(set)
    for node1, node2 in edges:
        edges_dict[node1].add(node2)
        edges_dict[node2].add(node1)

    res = []
    if not connect_nests_recursive(nests_set, edges_dict, res):
        return [-1]
    else:
        return res

#-------------------------------------------------------------------------------

# example
nests = [1, 3, 2, 5, 8, 6]
edges = [[3, 1], [3, 2], [3, 4], [3, 5], [3, 6], [4, 7], [7, 8], [1, 9]]
print(connect_nests(nests, edges))

#-------------------------------------------------------------------------------

import itertools

# Note: graph isomorphism is not taken into account
def gen_tree_edges(n):
    res = []
    gen_tree_edges_recursive(3, n, [[[1, 2]]], res)
    return res

def gen_tree_edges_recursive(i, n, subres, res):
    if i > n:
        res.extend(subres)
        return
    for j in range(1, i):
        gen_tree_edges_recursive(i + 1, n, [v + [[j, i]] for v in subres], res)

for n in range(2, 11):
    for q in range(2, n + 1, 2):
        print("N", n, "Q", q)
        for nests in itertools.combinations(list(range(1, n + 1)), q):
            for edges in gen_tree_edges(n):
                if connect_nests(nests, edges) == [-1]:
                    print(nests, edges)
Для поиска гнезд используется волновой алгоритм, так что сначала пытаются объединиться в пару ближайшие гнезда. Проверил работу на всех деревьях (но изоморфизм графов практически не учтен) с количеством вершин N от 2 до 10 и количеством гнезд от 2 до N (только четные) и не нашел случая, когда гнезда невозможно распределить.
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
BDA вне форума Ответить с цитированием
Старый 10.01.2024, 15:51   #10
ViktorR
Старожил
 
Регистрация: 23.10.2010
Сообщений: 2,338
По умолчанию

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

Спасибо, попробую разобраться в вашем коде.
Авось что-то пригодится для студентов.

PS: Ваше решение, в другой теме, с вложенными циклами и else, и командами break и continue буду использовать.
Как-то так, ...
ViktorR вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
По нажатию на кнопку Показать приложение должно открыть новое окно и показать в нем заказанные картинки с короткими подписями Zerroz JavaScript, Ajax 0 26.04.2017 23:56
Помогите составить блоксхему, препод не принимает вообще Spanchik Помощь студентам 1 23.12.2014 12:48
Проверьте пожалуйста код препод сказал, что не верен mital25 Помощь студентам 18 16.11.2014 20:48
Помогите пожалуйста создать код для этой задачи на Delphi 7 Viktor Makarov Помощь студентам 0 11.01.2014 09:26