bzoj2306 [Ctsc2011]幸福路径 倍增 Floyd

时间:2020-12-05 00:25:57

题目传送门

https://lydsy.com/JudgeOnline/problem.php?id=2306

题解

倍增 Floyd。

令 \(f[i][j][k]\) 表示走了 \(2^i\) 步,从 \(j\) 到 \(k\) 的距离最大值。

然后转移就是 \(f[i][j][k] = \max\limits_{l=1}^n f[i-1][j][l] + p \cdot f[i-1][l][k]\)。


另外要每一个点建立一个长度为 \(0\) 的自环,用来统计总的最大值。

#include<bits/stdc++.h>

#define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to)
#define dbg(...) fprintf(stderr, __VA_ARGS__)
#define File(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define fi first
#define se second
#define pb push_back template<typename A, typename B> inline char smax(A &a, const B &b) {return a < b ? a = b, 1 : 0;}
template<typename A, typename B> inline char smin(A &a, const B &b) {return b < a ? a = b, 1 : 0;} typedef long long ll; typedef unsigned long long ull; typedef std::pair<int, int> pii; template<typename I> inline void read(I &x) {
int f = 0, c;
while (!isdigit(c = getchar())) c == '-' ? f = 1 : 0;
x = c & 15;
while (isdigit(c = getchar())) x = (x << 1) + (x << 3) + (c & 15);
f ? x = -x : 0;
} const int N = 100 + 7;
const double INF = 1e18; int n, m, st;
double p;
double a[N], f[N][N][N]; inline void work() {
for (int i = 1; i <= 30; ++i, p = p * p)
for (int j = 1; j <= n; ++j)
for (int k = 1; k <= n; ++k)
for (int l = 1; l <= n; ++l) smax(f[i][j][k], f[i - 1][j][l] + p * f[i - 1][l][k]);
// for (int i = 0; i <= 30; ++i)
// for (int j = 1; j <= n; ++j)
// for (int k = 1; k <= n; ++k) dbg("f[%d][%d][%d] = %.10lf\n", i, j, k, f[i][j][k]);
double ans = 0;
for (int i = 1; i <= n; ++i) smax(ans, f[30][st][i]);
ans += a[st];
printf("%.1lf\n", ans);
} inline void init() {
read(n), read(m);
for (int i = 1; i <= n; ++i) scanf("%lf", &a[i]);
for (int i = 0; i <= 30; ++i)
for (int j = 1; j <= n; ++j) {
for (int k = 1; k <= n; ++k) f[i][j][k] = -INF;
f[i][j][j] = 0;
}
scanf("%d%lf", &st, &p);
int x, y;
for (int i = 1; i <= m; ++i) read(x), read(y), f[0][x][y] = p * a[y];
} int main() {
#ifdef hzhkk
freopen("hkk.in", "r", stdin);
#endif
init();
work();
fclose(stdin), fclose(stdout);
return 0;
}

bzoj2306 [Ctsc2011]幸福路径 倍增 Floyd的更多相关文章

  1. BZOJ2306&colon;&lbrack;CTSC2011&rsqb;幸福路径&lpar;倍增Floyd&rpar;

    Description 有向图 G有n个顶点 1,  2, …,  n,点i 的权值为 w(i).现在有一只蚂蚁,从给定的起点 v0出发,沿着图 G 的边爬行.开始时,它的体力为 1.每爬过一条边,它 ...

  2. 【bzoj2306】&lbrack;Ctsc2011&rsqb;幸福路径 倍增Floyd

    题目描述 一张n个点的有向图,每个点有一个权值.一开始从点$v_0$出发沿图中的边任意移动,移动到路径上的第$i$个点 输入 每一行中两个数之间用一个空格隔开. 输入文件第一行包含两个正整数 n,  ...

  3. BZOJ2306 &lbrack;Ctsc2011&rsqb;幸福路径&lbrack;倍增&rsqb;

    这个有环的情况非常的讨厌,一开始想通过数学推等比数列的和,但是发现比较繁就不做了. 然后挖掘这题性质. 数据比较小,但是体力可以很接近1(恼怒),也就是说可能可以跳很多很多步.算了一下,大概跳了2e7 ...

  4. BZOJ2306&colon; &lbrack;Ctsc2011&rsqb;幸福路径

    Description 有向图 G有n个顶点 1, 2, -, n,点i 的权值为 w(i).现在有一只蚂蚁,从 给定的起点 v0出发,沿着图 G 的边爬行.开始时,它的体力为 1.每爬过一条 边,它 ...

  5. 【BZOJ 2306】 2306&colon; &lbrack;Ctsc2011&rsqb;幸福路径 (倍增floyd)

    2306: [Ctsc2011]幸福路径 Time Limit: 10 Sec  Memory Limit: 256 MBSubmit: 912  Solved: 437 Description 有向 ...

  6. 【BZOJ2306】幸福路径(动态规划,倍增)

    [BZOJ2306]幸福路径(动态规划,倍增) 题面 BZOJ 题解 不要求确切的值,只需要逼近 显然可以通过移动\(\infty\)步来达到逼近的效果 考虑每次的一步怎么移动 设\(f[i][j]\ ...

  7. &lbrack;CTSC2011&rsqb;幸福路径

    题目描述 有向图 G有n个顶点 1, 2, …, n,点i 的权值为 w(i).现在有一只蚂蚁,从 给定的起点 v0出发,沿着图 G 的边爬行.开始时,它的体力为 1.每爬过一条 边,它的体力都会下降 ...

  8. BZOJ 2306&colon; &lbrack;Ctsc2011&rsqb;幸福路径

    Description 有向图 G有n个顶点 1, 2, -, n,点i 的权值为 w(i).现在有一只蚂蚁,从 给定的起点 v0出发,沿着图 G 的边爬行.开始时,它的体力为 1.每爬过一条 边,它 ...

  9. bzoj2165&colon; 大楼&lpar;倍增floyd&rpar;

    题目大意:一个有向图,n(<=100)个点求一条长度>=m(<=10^18)的路径最少经过几条边. 一开始以为是矩乘,蓝鹅当时还没开始写,所以好像给CYC安利错了嘿嘿嘿QWQ 第一眼 ...

随机推荐

  1. 一、基于hadoop的nginx访问日志分析---解析日志篇

    前一阵子,搭建了ELK日志分析平台,用着挺爽的,再也不用给开发拉各种日志,节省了很多时间. 这篇博文是介绍用python代码实现日志分析的,用MRJob实现hadoop上的mapreduce,可以直接 ...

  2. 安装php-amqplib(RabbitMQ的phpAPI)

    历史经验告诉我们,装逼没有好下场. 总结一下之前composer安装php-amqplib包失败的原因: composer安装的时候需要指定PHP执行文件的位置: PHP安装路径:/usr/local ...

  3. 【Mail】Tomcat提供JNDI方式支持JavaMail(三)

    流程介绍 Tomcat提供了JavaMail的支持,是通过JNDI的方式实现的,具体流程是: Tomcat启动的时候,自身产生一个Session对象,放在JNDI容器中给其他项目调用,其他项目只要通过 ...

  4. C-指针

    //格式:变量类型 *变量名//定义了一个指针变量p//指针变量只能存储地址//指针就一个作用:能够根据一个地址值,访问对应的存储空间//指针变量p前面的int:指针变量p只能指向int类型的数据in ...

  5. SVN和Maven及Jenkins&lpar;转&rpar;

    目前项目组在开发一个项目,由多个子模块构成,构建工具是maven,版本控制工具是svn.本文想对如何结合使用maven和svn提出一点初步的想法 一.只有svn的情况 首先考虑没有maven的情况.这 ...

  6. python webdriver安装

    前言 本次就python webdriver的安装和驱动不同浏览器的配置进行分享,以解决大家在入门过程中的一些基本的环境问题. python安装 目前python有2.x和3.x版本,笔者在这里推荐2 ...

  7. 一款好用的jquery评分插件

    一.使用说明 1.jQuery评分插件的功能: 图标显示用户评分,更美观 可实时点击,切换评分 返回用户评分,记录用户评分 实现类似下图效果 2.优点: 美观,方便 3.缺点: 只能用于jquery开 ...

  8. 好用的js模板

    组织form下的 json对象 $.fn.serializeObject = function() { var o = {"unique_id":new Date().getTim ...

  9. 从matlab中导出下载到的轨迹数据

    我从该网址(http://www.ee.cuhk.edu.hk/~xgwang/MITtrajsingle.html)下载到了一些轨迹数据. 网页中简单说明了轨迹数据的由来:原始数据是在一个停车场上方 ...

  10. JAVA基础知识之编译、运行、打包

    一:java环境设置在环境变量中设置以下三个变量: JAVA_HOME=C:\j2sdk1.4.1 //可以改为相应的目录CLASSPATH=%JAVA_HOME%\lib\tools.jar;%JA ...