找到你要的答案

Q:Isolating some vertices in a weighted tree with minimum cost

Q:用最小代价孤立加权树中的一些顶点

Suppose we are given a weighted tree and some set of vertices of that tree. The problem is to isolate those vertices(e.g. there should not be paths between them) by removing edges from the tree, such that the sum of the weights of removed edges is minimal.

I have been trying to solve this problem for about two hours, then I found solution in C++, but there was no explanation. As I understood it uses Dynamic Programming technique.

My question is what is the basic idea of solving this problem?

Thanks!

Here is the solution.

#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;
}

假设我们给出了一个加权树和一些树的顶点集。问题是隔离这些顶点(例如不应该有它们之间的路径),通过除去从树的边缘,使得除去的边缘的权重的总和是最小的。

我一直在试图解决了大约两个小时这个问题,然后我发现在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;
}
answer1: 回答1:

Formally, the problem is, given an acyclic undirected graph with weighted edges, together with a set of terminal vertices, find the minimum set of edges whose removal means that, for all pairs of distinct terminals, those terminals are no longer connected.

Root the graph arbitrarily and treat it as a general tree. We run a dynamic program that operates bottom-up on the vertices. Each vertex u has two labels: dp[u][0] is the minimum weight of edges to be removed in the subtree rooted at u so that no terminal in the subtree is connected to another terminal or to u, and dp[u][1] is the minimum removal weight that leaves exactly one subtree terminal connected to u. We have a recurrence

           { 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

taking an empty min to be infinity.

形式上,问题是,给定一个无环无向图的加权边缘,连同一组终端顶点,找到最小的一组边缘的去除意味着,对于所有对不同的终端,这些终端不再连接。

任意根图并将其视为一般树。我们运行一个动态的程序,自下而上的顶点上运行。每个顶点u有两个标签:DP [你]的[ 0 ]是边为根的子树,子树U没有终端连接到另一个终端或你删除的最小重量,和DP [美] [ 1 ]是最小的去除重量,叶子整整一子树终端与美国有复发

           { 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

以空分钟为无穷大。

c++  algorithm  dynamic-programming