以最小成本隔离加权树中的某些顶点

Question

假设我们得到了一棵加权树和该树的一些顶点集。问题是通过从树中移除边来隔离那些顶点（例如，它们之间不应该有路径），这样移除边的权重之和最小。

我已经尝试解决这个问题大约两个小时了，然后我在 C++ 中找到了解决方案，但没有任何解释。据我了解，它使用动态编程技术。

我的问题是解决这个问题的基本思路是什么？

谢谢！

这是解决方案。

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

#define PB push_back
#define MP make_pair

typedef long long LL;
const int MAXN = 100005;
const LL inf = 1LL << 55;
int N, K;
bool bad[MAXN];
LL dp[MAXN][2];
vector<pair<int, int> > adj[MAXN];

void dfs(int u, int fa) {
    dp[u][1] = 0;
    dp[u][0] = bad[u] ? inf : 0;

    for (int i = 0; i < adj[u].size(); i++) {
        int v = adj[u][i].first, w = adj[u][i].second;

        if (v != fa) {
            dfs(v, u);
            dp[u][1] += min(dp[v][0], dp[v][1] + w);
            dp[u][1] = min(dp[u][1], dp[u][0] + dp[v][1]);

            if (!bad[u])
                dp[u][0] += min(dp[v][0], dp[v][1] + w);
        }
    }
}

int main() {
    cin >> N >> K;

    for (int i = 1; i < N; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].PB(MP(b, c)); adj[b].PB(MP(a, c));
    }

    memset(bad, false, sizeof(bad));

    for (int i = 0; i < K; i++) {
        int x;
        cin >> x;
        bad[x] = true;
    }

    dfs(0, -1);
    LL ret = min(dp[0][0], dp[0][1]);

    cout << ret << endl;

    return 0;
}

Answer 1

形式上，问题是，给定一个带有加权边的无环无向图，以及一组 terminal 顶点，找到最小的边集，其删除意味着，对于所有成对的不同终端，这些终端不再连接。

任意根图，把它当成一般树。我们运行一个在顶点上自下而上运行的动态程序。每个顶点 u 有两个标签： dp[u][0] 是以 u 为根的子树中要删除的边的最小权重，以便子树中没有终端连接到另一个终端或 u，而dp[u][1]是恰好留下一个连接到u的子树终端的最小移除权重。我们有复发

           { infinity                  if v is a terminal
dp[u][0] = {       sum       dp[v][0]  otherwise
           { children v of u

dp[u][1] =       min       dp[v][1] +          sum          min(dp[w][0], dp[w][1] + weight(uw)),
           children v of u            other children w of v

将空的最小值设为 infinity。

以最小成本隔离加权树中的某些顶点

Isolating some vertices in a weighted tree with minimum cost

c++

algorithm

dynamic-programming