Нахождение отдельных сумм всех возможных деревьев после удаления ребер - PullRequest
Новая
       50

Нахождение отдельных сумм всех возможных деревьев после удаления ребер

0 голосов
/ 06 февраля 2019

Учитывая дерево с N узлами с ненулевыми весами узлов, сколько деревьев (удаляющих один или несколько ребер) этого дерева будет иметь сумму весов как x (дано)?

Например:

N = 3, вес каждой вершины равен 1 1 1, x = 2

ребер

1 2

2 3

теперь, удаляя 1-2, мы имеем 2 дерева 1 и 2-3 с суммой весов 1 и 2 соответственно, мы удаляем ребро 2-3, у нас есть 1-2 и 3 с суммой 2 и 1, таким образом, всего 2 деревасреди всех возможных деревьев (после удаления одного или нескольких ребер) с суммой веса, равной 2.

Мое решение -:

Я могу только найти решение грубой силы со сложностью2 ^ n (где n может достигать 10 ^ 5).

Грубая сила -: обрезать каждое ребро и применить bfs / dfs ко всем сформированным деревьям, добавить соответствующие веса вершин и проверитьесли сумма равна x.

Я думаю, что это можно оптимизировать, используя памятку DP, но я не могу придумать рекуррентное отношение.

Я тоже пробовал алгоритм min-cut, но он не применим здесь, насколько я понимаю. 

int bfs()
{
    for(each cut in 2^n using bitmask)
    {
        queue <int> q;
        q.push(s);
        vis[ s ] = true;
        while(!q.empty())
        {
            int p = q.front();
            q.pop();
            for(int i = 0;i < v[ p ].size() ; i++)
            {
                if(vis[ v[ p ][ i ] ] == false)
                {
                    sum+=w[p][i]; // weight of p-i edge is w[p][i]                  
                    q.push(v[ p ][ i ]);
                    vis[ v[ p ][ i ] ] = true;
                }
            }        
        }
    }
}

Есть ли какой-нибудь лучший алгоритм / оптимизация выше 2 ^ n решения, в зависимости от вопросаесть решение O (n) или O (n * logn).

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

...