diff options
Diffstat (limited to '05-advanced_algorithms_and_complexity/04-np-completeness/02-plan_party')
7 files changed, 42 insertions, 11 deletions
diff --git a/05-advanced_algorithms_and_complexity/04-np-completeness/02-plan_party/plan_party.cpp b/05-advanced_algorithms_and_complexity/04-np-completeness/02-plan_party/plan_party.cpp index 70249aa..f612252 100644 --- a/05-advanced_algorithms_and_complexity/04-np-completeness/02-plan_party/plan_party.cpp +++ b/05-advanced_algorithms_and_complexity/04-np-completeness/02-plan_party/plan_party.cpp @@ -1,5 +1,6 @@ #include <iostream> #include <vector> +#include <sys/resource.h> struct Vertex { int weight; @@ -27,23 +28,39 @@ Graph ReadTree() { return tree; } -void dfs(const Graph &tree, int vertex, int parent) { - for (int child : tree[vertex].children) - if (child != parent) - dfs(tree, child, vertex); - - // This is a template function for processing a tree using depth-first search. - // Write your code here. - // You may need to add more parameters to this function for child processing. +int dfs(const Graph &tree, int vertex, int parent, std::vector<int> &w) { + if ( w[vertex] == -1) { + if (tree[vertex].children.size() == 0) { + w[vertex] = tree[vertex].weight; + } else { + int m0 = tree[vertex].weight; + for (int child : tree[vertex].children) { + if (child != parent) { + for (int gchild : tree[child].children) { + if (gchild != child && gchild != vertex) { + m0 += dfs(tree, gchild, child, w); + } + } + } + } + int m1 = 0; + for (int child : tree[vertex].children) { + if (child != parent) { + m1 += dfs(tree, child, vertex, w); + } + } + w[vertex] = std::max(m0, m1); + } + } + return w[vertex]; } int MaxWeightIndependentTreeSubset(const Graph &tree) { size_t size = tree.size(); if (size == 0) return 0; - dfs(tree, 0, -1); - // You must decide what to return. - return 0; + std::vector<int> w(size, -1); + return dfs(tree, 0, -1, w); } int main() { diff --git a/05-advanced_algorithms_and_complexity/04-np-completeness/02-plan_party/tests/01 b/05-advanced_algorithms_and_complexity/04-np-completeness/02-plan_party/tests/01 new file mode 100644 index 0000000..4f88743 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/04-np-completeness/02-plan_party/tests/01 @@ -0,0 +1,2 @@ +1 +1000 diff --git a/05-advanced_algorithms_and_complexity/04-np-completeness/02-plan_party/tests/01.a b/05-advanced_algorithms_and_complexity/04-np-completeness/02-plan_party/tests/01.a new file mode 100644 index 0000000..83b33d2 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/04-np-completeness/02-plan_party/tests/01.a @@ -0,0 +1 @@ +1000 diff --git a/05-advanced_algorithms_and_complexity/04-np-completeness/02-plan_party/tests/02 b/05-advanced_algorithms_and_complexity/04-np-completeness/02-plan_party/tests/02 new file mode 100644 index 0000000..0777210 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/04-np-completeness/02-plan_party/tests/02 @@ -0,0 +1,3 @@ +2 +1 2 +1 2 diff --git a/05-advanced_algorithms_and_complexity/04-np-completeness/02-plan_party/tests/02.a b/05-advanced_algorithms_and_complexity/04-np-completeness/02-plan_party/tests/02.a new file mode 100644 index 0000000..0cfbf08 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/04-np-completeness/02-plan_party/tests/02.a @@ -0,0 +1 @@ +2 diff --git a/05-advanced_algorithms_and_complexity/04-np-completeness/02-plan_party/tests/03 b/05-advanced_algorithms_and_complexity/04-np-completeness/02-plan_party/tests/03 new file mode 100644 index 0000000..4867a3e --- /dev/null +++ b/05-advanced_algorithms_and_complexity/04-np-completeness/02-plan_party/tests/03 @@ -0,0 +1,6 @@ +5 +1 5 3 7 5 +5 4 +2 3 +4 2 +1 2 diff --git a/05-advanced_algorithms_and_complexity/04-np-completeness/02-plan_party/tests/03.a b/05-advanced_algorithms_and_complexity/04-np-completeness/02-plan_party/tests/03.a new file mode 100644 index 0000000..b4de394 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/04-np-completeness/02-plan_party/tests/03.a @@ -0,0 +1 @@ +11 |