当前位置: 首页 > 工具软件 > station-power > 使用案例 >

poj - 4045 - Power Station(树形dp)

岳锦
2023-12-01

题意:一棵有n个结点的树,要取其中的一个结点,使得该结点到其他所有结点的距离和dis最小,即损耗I * I * R * dis最小,输出最小损耗和该结点(有多个的话按结点编号从小到大输出)(3 <= n <= 50000, 1 <= I <= 10, 1 <= R <= 50)。

题目链接:http://poj.org/problem?id=4045

——>>怒刷树状dp。。。

设cnt[i]为以i为根的子树的结点数,d[i]为以i为根的子树中所有结点到i的距离和,一次dfs求出*cnt和*d,则

状态转移方程为:cnt[x] += cnt[v[e]];

d[x] += d[v[e]] + cnt[v[e]];(v[e]为x的子结点)

设f[i]为以i为根,刚才dfs中i的父结点为孩子,新生子树中所有结点到i的距离和,再一次dfs,即dp,则

状态转移方程为:f[x] = d[fa] - d[x] - cnt[x] + f[fa] + n -cnt[x] = d[fa] - d[x] - 2 * cnt[x] + f[fa] + n;(x为第一次dfs中fa的子结点)。

注意:用64位整数

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn = 50000 + 10;
const int INF = 0x3f3f3f3f;
int n, I, R, head[maxn], nxt[maxn<<1], u[maxn<<1], v[maxn<<1], ecnt, cnt[maxn];
long long d[maxn], f[maxn];

void init(){
    ecnt = 0;
    memset(head, -1, sizeof(head));
}

void addEdge(int uu, int vv){
    u[ecnt] = uu;
    v[ecnt] = vv;
    nxt[ecnt] = head[uu];
    head[uu] = ecnt;
    ecnt++;
}

void read(){
    int i, uu, vv;
    scanf("%d%d%d", &n, &I, &R);
    for(i = 0; i < n-1; i++){
        scanf("%d%d", &uu, &vv);
        addEdge(uu, vv);
        addEdge(vv, uu);
    }
}

void dfs(int x, int fa){
    d[x] = 0;
    for(int e = head[x]; e != -1; e = nxt[e]) if(v[e] != fa){
        dfs(v[e], x);
        cnt[x] += cnt[v[e]];
        d[x] += d[v[e]] + cnt[v[e]];
    }
}

void dp(int x, int fa){
    if(x == 1) f[x] = 0;
    else f[x] = d[fa] - d[x] - 2 * cnt[x] + f[fa] + n;
    for(int e = head[x]; e != -1; e = nxt[e]) if(v[e] != fa) dp(v[e], x);
}

void solve(){
    int i, flag = 1;
    long long Min = INF;
    for(int i = 1; i <= n; i++) cnt[i] = 1;
    dfs(1, -1);
    dp(1, -1);
    for(i = 1; i <= n; i++) Min = min(Min, d[i] + f[i]);
    printf("%I64d\n", I * I * R * Min);
    for(i = 1; i <= n; i++) if(d[i] + f[i] == Min) {
        if(flag) flag = 0;
        else putchar(' ');
        printf("%d", i);
    }
    puts("\n");
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--){
        init();
        read();
        solve();
    }
    return 0;
}




 类似资料: