1065: [NOI2008] 奥运物流

Description

2008北京奥运会即将开幕，举国上下都在为这一盛事做好准备。为了高效率、成功地举办奥运会，对物流系统

进行规划是必不可少的。物流系统由若干物流基站组成，以 1 … N 进行编号。每个物流基站 i 都有且仅有一个

后继基站 Si，而可以有多个前驱基站。基站 i 中需要继续运输的物资都将被运往后继基站 Si，显然一个物流基

站的后继基站不能是其本身。编号为 1 的物流基站称为控制基站，从任何物流基站都可将物资运往控制基站。注

意控制基站也有后继基站，以便在需要时进行物资的流通。在物流系统中，高可靠性与低成本是主要设计目。对于

基站 i ，我们定义其"可靠性"R(i) 如下：设物流基站 i 有 w 个前驱基站 P1,P2, ...Pw ，即这些基站以 i

为后继基站，则基站 i 的可靠性 R(i) 满足下式：

$ R(i) = C_i + k \sum_{j=1}^w R(P_j) $

其中 Ci 和 k 都是常实数且恒为正，且有 k 小于 1 。整个系统的可靠性与控制基站的可靠性正相关，我们

的目标是通过修改物流系统，即更改某些基站的后继基站，使得控制基站的可靠性 R(1) 尽量大。但由于经费限制

，最多只能修改 m 个基站的后继基站，并且，控制基站的后继基站不可被修改。因而我们所面临的问题就是，如

何修改不超过 m 个基站的后继，使得控制基站的可靠性 R(1) 最大化。

Input

　　输入第一行包含两个整数与一个实数，N，m，k。其中 N 表示基站数目，m 表示最多可修改的后继基站数目，

k 分别为可靠性定义中的常数。第二行包含 N 个整数，分别是 S1,S2...SN ，即每一个基站的后继基站编号。第三

行包含 N 个正实数，分别是 C1,C2...CN ，为可靠性定义中的常数

Output

　　输出仅包含一个实数，为可得到的最大 R(1)。精确到小数点两位

Sample Input

4 1 0.5

2 3 1 3

10.0 10.0 10.0 10.0

Sample Output

30.00

HINT

　　对于所有的数据，满足 m≤N≤60，Ci≤106，0.3≤k < 1,请使用双精度实数，无需考虑由此带来的误差。

题解

此题可以参照徐源盛《对一类动态规划问题的研究》

此题由于说从任何物流基站都可将物资运往控制基站，所以图为一个带有一个环的有向连通图。

设$dp[i][j][k]$表示第$i$个节点的子树中修改了$j$个节点且$i$到1的距离为$k$。

如若修改$i$节点，则$dp[i][j][k] = max(\sum_{i=1}^w dp[son_i][j_i][2]) | (\sum_{i=1}^w j_i) = j$

如果不修改$i$节点，则$dp[i][j][k] = max(\sum_{i=1}^w dp[son_i][j_i][k+1]) | (\sum_{i=1}^w j_i) = j$

在更新$dp$值时用背包优化就好了。

我在initi时初始化没更新全，WA了好几发

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int N = 65;

const double oo = 1e22;

int Nxt[N], to[N], nxt[N], head[N], totE, n, m, Siz[N];

#define Adde(a,b) (to[totE] = b, nxt[totE] = head[a], head[a] = totE++)

double kk[N], dp[N][N][N], C[N], tmp[N][N], k, _MinT;

#define cans(a) ((_MinT = (a)) > ans ? ans = _MinT : 1)

void init() {

	for (int i = 0; i <= n; head[i++] = -1)

	  for (int j = 0; j <= n; ++j)

		for (int k = 0; k <= n; ++k)

		  dp[i][j][k] = -oo;

	totE = 0;

}

void Cal(int u, int dep) {

	for (int i = 0; i <= Siz[u]; ++i)

	  for (int j = 0; j <= m; ++j)

		tmp[i][j] = -oo;

	tmp[0][0] = 0.;

	for (int i = head[u], s = 1; ~i; i = nxt[i], ++s) {

		int v = to[i];

		for (int j = 0; j <= m; ++j)

			for (int k = 0; k <= j; ++k)

				tmp[s][j] = max(tmp[s][j], tmp[s-1][k] + dp[v][j-k][dep]);

	}

}

void dfs(int u) {

	Siz[u] = 0;

	for (int i = head[u]; ~i; i = nxt[i], ++Siz[u]) dfs(to[i]);

	Cal(u, 2);

	for (int i = 0; i <= n; ++i)

	  for (int j = 1; j <= m; ++j)

		dp[u][j][i] = tmp[Siz[u]][j-1] + C[u] * k;//直接将此站接到1后面

	for (int i = 0; i <= n; ++i) {

		Cal(u, i + 1);

		for (int j = 0; j <= m; ++j)

		  dp[u][j][i] = max(dp[u][j][i], tmp[Siz[u]][j] + C[u] * kk[i]);

	}

}

int main() {

	scanf("%d%d%lf", &n, &m, &k);

	for (int i = 1; i <= n; ++i) scanf("%d", Nxt + i);

	for (int i = 1; i <= n; ++i) scanf("%lf", C + i);

	kk[0] = 1; kk[1] = k;

	double ans = -oo;

	for (int i = 2; i < N; ++i) kk[i] = kk[i-1] * k;

	for (int i = Nxt[1], len = 2, j; i ^ 1; i = Nxt[i], ++len) {

		init();

		for (j = 2; j <= n; ++j)

		  if (j ^ i) Adde(Nxt[j], j); else Adde(1, j);

		dfs(1);

		cans(dp[1][m - (Nxt[i] != 1)][0] / (1. - kk[len]));

	}

	printf("%.2lf\n", ans);

	return 0;

}

物流

bzoj 1065: [NOI2008] 奥运物流