ВСЕ ОТЛИЧНО
Информация о работе
Подробнее о работе
Задача C++; Выбор вершин взвешенного дерева
- 1 страниц
- 2020 год
- 25 просмотров
- 3 покупки
Гарантия сервиса Автор24
Уникальность не ниже 50%
Фрагменты работ
Дан граф, являющийся деревом. В вершинах графа написаны целые числа. Множество вершин графа называется допустимым, если никакие две вершины этого множества не соединены ребром.
Рассмотрим все допустимые множества вершин графа. Для каждого такого множества вычислим сумму чисел, написанных в его вершинах. Какова максимальная из этих сумм?
Формат файла входных данных:
Граф в этой задаче задан в виде корневого дерева. В графе выделена вершина - корень дерева. Для каждой вершины i, не являющейся корнем, задан номер вершины-предка pi в корневом дереве. Дерево, заданное таким образом, состоит из рёбер i-pi для всех вершин i, кроме корня.
В первой строке входного файла записано целое число n - количество вершин в графе (1
#include
#include
#include
#include
using namespace std;
vector a;
vector q;
vector color;
vector dg;
vector db;
int n;
void dfs(int v)
{
color[v] = 1;
dg[v] = 0;
db[v] = q[v];
for (int i = 0; i < a[v].size(); i++)
{
int u =a[v][i];
if (!color[u])
Задача C++; Выбор вершин взвешенного дерева
Дан граф, являющийся деревом. В вершинах графа написаны целые числа. Множество вершин графа называется допустимым, если никакие две вершины этого множества не соединены ребром.
Рассмотрим все допустимые множества вершин графа. Для каждого такого множества вычислим сумму чисел, написанных в его вершинах. Какова максимальная из этих сумм?
Формат файла входных данных:
Граф в этой задаче задан в виде корневого дерева. В графе выделена вершина - корень дерева. Для каждой вершины i, не являющейся корнем, задан номер вершины-предка pi в корневом дереве. Дерево, заданное таким образом, состоит из рёбер i-pi для всех вершин i, кроме корня.
В первой строке входного файла записано целое число n - количество вершин в графе (1
графы, динамическое программирование
Форма заказа новой работы
Не подошла эта работа?
Закажи новую работу, сделанную по твоим требованиям
