题解 P4202 【[NOI2008]奥运物流 】

· · 题解

个人博客链接

思路：

　　单独考虑每个点对答案的贡献，设 d_i 表示 i 到 1 的距离，那么它产生的贡献就是 k^{d_i}C_i 再加上环对答案的影响，所以 R(1) = \frac{\sum_{i=1}^n k^{d_i}C_i}{1-k^{len}},len 为环长。 　　这样的话，不难发现每次修改肯定是把一个点连到 1 的下面。 　　设 dp[o][m][d] 表示在 o 子树内当 o 的深度为 d 还有 m 次修改机会时的最大可靠值。在树上的修改就是一个类似背包的 \text{dp} 复杂度 O(n^4)。 　　但是如果对环做修改就会影响下面的分母。所以还要再枚举环长，每次重新 \text{dp}，所以复杂度就是 O(n^5) 的。

代码：

#include <bits/stdc++.h>
#define File(_) freopen(#_ ".in", "r", stdin), freopen(#_ ".out", "w", stdout)
#define ALL(x) x.begin(), x.end()
#define mset(a, b) memset(a, b, sizeof a)
#define rep(i, a, b) for(int i(a), i##_END_(b); i <= i##_END_; i++) 
#define drep(i, a, b) for(int i(a), i##_END_(b); i >= i##_END_; i--)
using namespace std;
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}
typedef long long ll;
typedef double db;

const int N = 65;

template<int N, int M, class T> struct Link {
#define erep(k, G, o) for(int k(G.HEAD[o]); k; k = G.NXT[k])
    int HEAD[N], NXT[M], tot; T W[M];
    void clear() {mset(HEAD, 0); tot = 0;}
    void add(int x, T w) {NXT[++tot] = HEAD[x]; W[HEAD[x] = tot] = w;}
    T& operator[] (int k) {return W[k];}
};
Link<N, N * 2, int> G;

int s[N];
db c[N], k;

db dp[N][N][N], tmp[N][N];
db pw[N];
void dfs(int o, int m, int dep) {
    rep(i, 0, m) rep(d, 0, dep) dp[o][i][d] = c[o] * pw[d];
    erep(k, G, o) {
        int v = G[k];
        dfs(v, m, dep + 1);
        mset(tmp, 0);
        rep(i, 0, m) rep(j, 0, m - i) rep(d, 0, dep) {
            tomax(tmp[i + j][d], dp[o][i][d] + dp[v][j][d + 1]);
            if(j > 0) tomax(tmp[i + j][d], dp[o][i][d] + dp[v][j - 1][1]);
        }
        rep(i, 0, m) rep(d, 0, dep) dp[o][i][d] = tmp[i][d];
    }
}
db calc(int m) {
    dfs(1, m, 0);
    return dp[1][m][0];
}

int main() {
    File(trans);
    int n, m;
    scanf("%d%d%lf", &n, &m, &k);
    pw[0] = 1.0; rep(i, 1, n) pw[i] = pw[i - 1] * k;
    rep(i, 1, n) scanf("%d", &s[i]);
    rep(i, 1, n) scanf("%lf", &c[i]);
    db ans = 0;
    for(int d = 2, p = s[1]; p != 1; d++, p = s[p]) {
        G.clear();
        int t = s[p]; s[p] = 1;
        rep(i, 2, n) G.add(s[i], i);
        tomax(ans, calc(m - (t != s[p])) / (1 - pw[d]));
        s[p] = t;
    }
    printf("%.2lf\n", ans);
    return 0;
}