P1364 医院设置题解

题意

找一个点使得所有点到它的距离最短。

所有点到它的距离计算方法是其他所有点的人口乘以到这个点的距离之和。

注意！这题没有边权！只有点权（我第一次就栽在这里[捂脸哭笑]）。

思路

有两种方法，暴力和换根dp。

暴力很简单，由于 $n$ 很小，直接遍历 $1 \thicksim n$ 为根dfs后一遍算出的距离之和取最小值。

换根dp就是先dfs出以 $1$ 为根的距离之和，在dfs以其他节点为跟的距离之和取最小值。

那么状态转移方程是什么呢？

看下题目中的图，如果把医院改 $3$ 号点，不就是左边的 $1, 2$ 号点多走了，右边的 $3, 4, 5$ 号点少走了？

所以很容易推出状态转移方程是：

$f[v]=f[u]+size[1]−size[v]−size[v]$

完活！

Code

//暴力写法
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector <int> wth[105];
int ans = 1e9, cnt[105], hz[105];
int a[105];
void dfs(int now, int f, int dep, int rt)
{
    cnt[now] = hz[now];
    a[rt] += hz[now] * dep;
    for(auto v : wth[now])
    {
        if(v == f)
        {
            continue;
        }
        dfs(v, now, dep + 1, rt);
        cnt[now] += cnt[v];
    }
}
int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        int u, v, w;
        cin >> w >> u >> v;
        hz[i] = w;
        if(u != 0)
        {
            wth[i].push_back(u);
            wth[u].push_back(i);
        }
        if(v != 0)
        {
            wth[i].push_back(v);
            wth[v].push_back(i);
        }
    }
    for(int i = 1; i <= n; i++)
    {
        dfs(i, 0, 0, i);
        ans = min(ans, a[i]);
    }
    cout << ans;
    return 0;
}

朴实无华的分割“字”

//换根dp写法
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector <int> wth[105];
int ans = 1e9, cnt[105], hz[105];
int a[105];
void dfs(int now, int f, int dep)
{
    cnt[now] = hz[now];
    a[1] += hz[now] * dep;
    for(auto v : wth[now])
    {
        if(v == f)
        {
            continue;
        }
        dfs(v, now, dep + 1);
        cnt[now] += cnt[v];
    }
}
void dfs2(int u, int f)
{
    if(u != 1)
    {
        a[u] = a[f] + (cnt[1] - cnt[u]) - cnt[u];
    }
    ans = min(ans, a[u]);
    for(auto v : wth[u])
    {
        if(v == f)
        {
            continue;
        }
        dfs2(v, u);
    }
}
int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        int u, v, w;
        cin >> w >> u >> v;
        hz[i] = w;
        if(u != 0)
        {
            wth[i].push_back(u);
            wth[u].push_back(i);
        }
        if(v != 0)
        {
            wth[i].push_back(v);
            wth[v].push_back(i);
        }
    }
    dfs(1, 0, 0);
    dfs2(1, 0);
    cout << ans;
    return 0;
}

第一次写题解，有不严谨之处望指出=D