P1364 医院设置

floyd

用floyd求出任意一个两个点之间的最短距离，然后算一下以所有节点为根的情况下的距离之和最小值。
复杂度：(O(n^3))

#include<iostream>
#include<cstring>

using namespace std;

const int N = 110, INF = 0x3f3f3f3f;

int n;
int g[N][N];
int w[N];

int main(){
    memset(g, 0x3f, sizeof g);
    
    cin >> n;
    
    for(int i = 1; i <= n; i ++){
        int a, b;
        cin >> w[i] >> a >> b;
        g[i][a] = g[i][b] = g[a][i] = g[b][i] = 1;
    }
    
    for(int i = 1; i <= n; i ++) g[i][i] = 0;
    
    for(int k = 1; k <= n; k ++)
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= n; j ++)
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
                
    int res = INF;
    
    for(int i = 1; i <= n; i ++){
        int ans = 0;
        for(int j = 1; j <= n; j ++)
            if(i != j) ans += g[i][j] * w[j];
        
        res = min(res, ans);
    }
    
    cout << res;
                
    return 0;
}

树的重心

需要预处理出：

1. 以一个结点为整棵树的根u（这个可以任选，这里选1，这个和后面的递推起点有关）的情况下，以每一个结点v为根的子树包括的所有人口s[v]
2. 将医院建在1号点时的总距离f(1)

递推方法：(f[v] = f[u] - s[v] + s[1] - s[v];)，f[k]表示把医院建在k的总距离，s[k]表示包括k在内的以k为根的子树。
解释：
v为u的出边所到达的点，现在已知将医院建在u时的总距离f[u], 既然v为u的出边，那么以v为根的子树（包括v）本来是走到u的而现在只需要到v，那么就先需要将f[u]减去s[v], 而除去v的子树的所有节点（包括v）原本是要走到u的，而现在需要走到v，那么f[u]还需要加上s[1] (总人口) - s[v]

复杂度：(O(n))

#include<iostream>
#include<cstring>
#include<queue>

using namespace std;

const int N = 110, INF = 0x3f3f3f3f;

struct Node{
    int l, r;
    int w;
}tr[N];

int n;
int s[N];
int f[N];
int level[N];

int dfs_1(int u){
    if(u == 0) return 0;
    s[u] += dfs_1(tr[u].l) + dfs_1(tr[u].r) + tr[u].w;
    return s[u];
}


void dfs_2(int u){
    int l = tr[u].l, r = tr[u].r;
    if(l){
        f[l] = f[u] - s[l] + s[1] - s[l];
        dfs_2(l);
    }
    
    if(r){
        f[r] = f[u] - s[r] + s[1] - s[r];
        dfs_2(r);
    }
}


int main(){
    cin >> n;
    
    for(int i = 1; i <= n; i ++){
        int l, r, w;
        cin >> w >> l >> r;
        
        tr[i] = {l, r, w};
    }
    
    dfs_1(1);
    
    memset(f, 0x3f, sizeof f);
    
    queue<int> q;
    
    q.push(1);
    level[1] = 0;
    f[1] = 0;
    
    while(q.size()){
        int h = q.front();
        q.pop();
        
        int l = tr[h].l, r = tr[h].r;
        level[l] = level[r] = ++ level[h];
        if(l) f[1] += tr[l].w * level[l], q.push(l);
        if(r) f[1] += tr[r].w * level[r], q.push(r);
    }
    
    dfs_2(1);
    
    int res = INF;
    
    for(int i = 1; i <= n; i ++) res = min(res, f[i]);
    
    cout << res;
    
    return 0;
}