Menu
Article ACM

HDU4118 这也算树形DP？

NodeKey

NodeKey

• 2 min read

传送门

题意：

给你一个无向图，保证联通并且没有环（实质上就是一棵树……），要求：
每个点移动到另一个点去，并且不可能会有两个点移动到同一个点去，求最大移动距离和。

思路：

队友告诉我是图论……
…………
然后我特么还信了……
……………………

在看到结点个数达到 1e5 的时候我就应该意识到，基本不会是什么图论算法了。

我们可以这么想，先只考虑一半的节点移动到另一半的节点。
再是我们得确认一点，假如我可以得到这棵树的重心，那么重心一边的节点必然得移动到重心另一边的节点去才能使得移动距离和最大。（这个是显然的吧……举个例子 a-b-c-d a->c 必然会比 a->b 距离和大，而且，a->b影响的是 a,b 两个节点。）
然而我们无法轻松找到一棵树的重心，但是，我们从每一条边进行考虑，要使移动距离和最大，由该边断开形成的两棵子树，节点数目小的那一棵必然会全部移动到结点数目更多的那一棵，因为树的重心必然在节点数目更多的那一棵子树上，而且反过来移动也是不可能的吧…………

于是我们只要一次dfs就好了……

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 5;

int n, idx;
int head[maxn];
int node_num[maxn];
long long ans;

struct node {
    int to;
    int dis;
    int nxt;
} edges[maxn << 1];

void addEdge(int u, int v, int w)
{
    edges[idx].to = v;
    edges[idx].dis = w;
    edges[idx].nxt = head[u];
    head[u] = idx++;
}

void init()
{
    for (int i = 0; i <= n; i++) {
        head[i] = -1;
        node_num[i] = 0;
    }
    idx = 0;
    ans = 0;
}

int tree_dp(int cur, int pre)
{
    int total = 1, v, tmp;
    for (int it = head[cur]; ~it; it = edges[it].nxt) {
        v = edges[it].to;
        if (v != pre) {
            tmp = tree_dp(v, cur);
            ans += min(tmp, n - tmp) * edges[it].dis * 2; //因为来回，所以乘2
            total += tmp;
        }
    }
    return total;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int T, u, v, w;
    cin >> T;
    for (int cas = 1; cas <= T; cas++) {
        cin >> n;
        init();
        for (int i = 1; i < n; i++) {
            cin >> u >> v >> w;
            addEdge(u, v, w);
            addEdge(v, u, w);
        }
        tree_dp(1, -1);
        printf("Case #%d: %lld\n", cas, ans);
    }
    return 0;
}

很多题解都说是 树形DP ，为什么我指示觉得就是一个 DFS …… 虽然很有我之前学得模板风格

顺带一提的是，网上的题解质量真是越來越差了，很多核心部分的代码，直接一个显然得就没了……然后没多大卵用的东西瞎扯一堆……

Share