Это задача с XXX Польской олимпиады по информатике II этапа под названием «Вспиначка». Ссылка на исходную постановку задачи на польском языке.Давайте превратим приведенную выше историю в формулировку алгоритмической задачи:
Данный направленный ациклический граф (DAG) g , для каждой вершины p в этом графе g вычислим сумму всех достижимых узлов, если мы начнем движение от p. Значения узлов задаются в виде массива, где i-е значение соответствует i-й вершине.
Известно, что когда мы находимся в вершине i, то направленное ребро из от узла i до узла j существует только если j > i.
Кроме того, нам дано k, 1 > beauty;
vector adj_list(n);
vector reversed_adj_list(n);
vector outgoing_edges(n);
for (int i = 0; i < m; ++i)
{
int a, b;
cin >> a >> b;
--a;
--b;
adj_list[a].push_back(b);
reversed_adj_list.push_back(a);
++outgoing_edges[a];
}
queue q;
for (int i = 0; i < n; ++i)
{
if (outgoing_edges == 0)
{
q.push(i);
}
}
vector dp(n);
while (!q.empty())
{
int node = q.front();
q.pop();
dp[node] = beauty[node];
for (const int child : adj_list[node])
{
dp[node] += dp[child];
}
for (const int parent : reversed_adj_list[node])
{
--outgoing_edges[parent];
if (outgoing_edges[parent] == 0)
{
q.push(parent);
}
}
}
for (int i = 0; i < n; ++i)
cout когда я начнем с узла 1, расчетный ответ – 14, потому что я дважды посчитал узел 4.
Я понятия не имею, как избежать этой ситуации, и Я не использовал маленькое значение k. Я знаю, что существует решение, которое использует dp[node][mask], где маска имеет значение до 2^K, но я не могу его найти. Временная сложность этого решения составляет O(n * 2^K + m) (m из-за чтения входных данных).
Подробнее здесь: https://stackoverflow.com/questions/792 ... n-dag-with
