bzoj1065: [NOI2008]奥运物流

传送门：http://blog.csdn.net/whjpji/article/details/7593329

const int N = 70;
int Fa[N], n, m;
DB Dp[N][N][N], S[N][N][N];
DB C[N], F[N], K[N], Ans;

inline void Input() {
	scanf("%d%d%lf", &n, &m, &K[1]);
	For(i, 2, n) K[i] = K[i - 1] * K[1];
	For(i, 1, n) scanf("%d", Fa + i);
	For(i, 1, n) scanf("%lf", C + i);
}

inline void Work(int x, int d) {
	For(i, 2, n)
		if(Fa[i] == x) Work(i, d + 1);
	For(i, min(2, d), d) {
		Rep(j, m + 1) F[j] = 0;
		For(j, 2, n)
			if(Fa[j] == x) {
				Ford(k, m, 0)
					Ford(l, k, 0) F[k] = max(F[k], F[l] + S[j][k - l][i]);
			}
		For(j, 0, m) Dp[x][j][i] = F[j] + C[x] * K[i];
	}
	if(d > 1) {
		For(i, 0, m) F[i] = 0;
		For(i, 2, n)
			if(Fa[i] == x) {
	   			Ford(j, m, 0)
					Ford(k, j, 0) F[j] = max(F[j], F[k] + S[i][j - k][1]);
			}
		For(i, 1, m) Dp[x][i][1] = F[i - 1] + C[x] * K[1];
	}
	For(i, 0, m)
		Rep(j, d) S[x][i][j] = max(Dp[x][i][j + 1], Dp[x][i][1]);
}
inline void Solve() {
	for(int Tab = Fa[1], len = 2; Tab - 1; Tab = Fa[Tab], ++len) {
		For(i, 1, n)
			For(j, 0, m)
				For(k, 0, n) Dp[i][j][k] = S[i][j][k] = 0;
		int tmp = Fa[Tab];
		DB Now = 0;
		Fa[Tab] = 1;
		For(i, 2, n)
			if(Fa[i] == 1) Work(i, 1);
		For(i, 0, m) F[i] = 0;
		For(i, 2, n)
			if (Fa[i] == 1) {
				Ford(j, m, 0)
					Ford(k, j, 0) F[j] = max(F[j], F[k] + Dp[i][j - k][1]);
			}
		Rep(i, m) Now = max(Now, F[i]);
		if(tmp == 1) Now = max(Now, F[m]);
		Ans = max(Ans, (Now + C[1]) / (1.0 - K[len])), Fa[Tab] = tmp;
	}
	printf("%.2lf\n", Ans);
}

int main() {
	#ifndef ONLINE_JUDGE
	SETIO("1065");
	#endif
	Input();
	Solve();
	return 0;
}