Chro's Blog


同じ世界に、立っていたんだ。


「BZOJ 2306」「CTSC2011」幸福路径

  1. 1. Description
  2. 2. Input
  3. 3. Output
  4. 4. Sample Input
  5. 5. Sample Output
  6. 6. HINT
  7. 7. Solution

Description

有向图 G有n个顶点 1, 2, …, n,点i 的权值为 w(i)。现在有一只蚂蚁,从给定的起点 v0出发,沿着图 G 的边爬行。开始时,它的体力为 1。每爬过一条边,它的体力都会下降为原来的 ρ 倍,其中ρ 是一个给定的小于1的正常数。而蚂蚁爬到某个顶点时的幸福度,是它当时的体力与该点权值的乘积。

我们把蚂蚁在爬行路径上幸福度的总和记为 H。很显然,对于不同的爬行路径,H 的值也可能不同。小 Z 对 H 值的最大可能值很感兴趣,你能帮助他计算吗?注意,蚂蚁爬行的路径长度可能是无穷的。

Input

每一行中两个数之间用一个空格隔开。

输入文件第一行包含两个正整数 n, m,分别表示 G 中顶点的个数和边的条数。

第二行包含 n个非负实数,依次表示 n个顶点权值 w(1), w(2), …, w(n)。

第三行包含一个正整数 v0,表示给定的起点。

第四行包含一个实数 ρ,表示给定的小于 1的正常数。

接下来 m行,每行两个正整数 x, y,表示是G的一条有向边。可能有自环,但不会有重边。

Output

仅包含一个实数,即 H值的最大可能值,四舍五入到小数点后一位。

Sample Input

1
2
3
4
5
6
7
8
9
5 5
10.0 8.0 8.0 8.0 15.0
1
0.5
1 2
2 3
3 4
4 2
4 5

Sample Output

1
18.0

HINT

对于 100%的数据, n ≤ 100, m ≤ 1000, ρ ≤ 1 – 10^-6, w(i) ≤ 100 (i = 1, 2, …, n)。

Solution

这 TM 都能出成 CTSC 题目?!


由于精度要求实在是……太低了,我们不必考虑「走无穷多步」的情况(随着时间推移,每一步的幸福度指数级减小),那就直接倍增 Floyd 算算走 $2^60$ 步的最优方案就好了……

dp[b][i][j] 表示从 i 开始走 $2^b$ 步到达 j 的最大幸福度。那么 $dp[b][i][j]=max\{dp[b-1][i][k]+dp[b-1][k][j]\}$。边界是 dp[0][i][i]=0(若存在该点的自环则等于 $w[i]\times\rho$),输入的每条边 $dp[0][x][y]=w[y]\times\rho$,其他值均为 $-\infty$。


强烈谴责卡评测行为!!!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
#define long long long
const int maxb = 61;
const int maxn = 103;
const double inf = 1e15;
int n, m, v;
double w[maxn], rho[maxb], dp[maxb][maxn][maxn];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) scanf("%lf", w + i);
scanf("%d%lf", &v, rho);
for (int i = 1; i < maxb; ++i) rho[i] = rho[i - 1] * rho[i - 1];
for (int b = 0; b < maxb; ++b) for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) dp[b][i][j] = -inf;
for (int i = 1; i <= n; ++i) dp[0][i][i] = 0.0;
for (int i = 1, x, y; i <= m; ++i) scanf("%d%d", &x, &y), dp[0][x][y] = w[y] * *rho;
for (int b = 1; b < maxb; ++b) for (int k = 1; k <= n; ++k)
for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j)
dp[b][i][j] = max(dp[b][i][j], dp[b - 1][i][k] + dp[b - 1][k][j] * rho[b - 1]);
double ans = 0.0;
for (int i = 1; i <= n; ++i) ans = max(ans, dp[maxb - 1][v][i]);
printf("%0.1lf\n", ans + w[v]);
return 0;
}
最近的文章

「BZOJ 2759」一个动态树好题

Description有N个未知数x[1..n]和N个等式组成的同余方程组: x[i]=k[i]*x[p[i]]+b[i] mod 10007 其中,k[i],b[i],x[i]∈[0,10007)∩Z 你要应付Q个事务,每个是两种情况之一: 一.询问当前x[a]的解 A a 无解输出-1 x[a]…

BZOJ, Link-Cut Tree, 基环树 继续阅读
更早的文章

「BZOJ 1025」「SCOI2009」游戏

Descriptionwindy学会了一种游戏。对于1到N这N个数字,都有唯一且不同的1到N的数字与之对应。最开始windy把数字按顺序1,2,3,……,N写一排在纸上。然后再在这一排下面写上它们对应的数字。然后又在新的一排下面写上它们对应的数字。如此反复,直到序列再次变为1,2,3,……,N。 如…

BZOJ, 群论, 背包 DP 继续阅读