[CTSC2011]幸福路径
2024-09-10 11:24:17
题目描述
有向图 G有n个顶点 1, 2, …, n,点i 的权值为 w(i)。现在有一只蚂蚁,从 给定的起点 v0出发,沿着图 G 的边爬行。开始时,它的体力为 1。每爬过一条 边,它的体力都会下降为原来的 ρ 倍,其中ρ 是一个给定的小于1的正常数。而 蚂蚁爬到某个顶点时的幸福度,是它当时的体力与该点权值的乘积。
我们把蚂蚁在爬行路径上幸福度的总和记为 H。很显然,对于不同的爬行路 径,H 的值也可能不同。小 Z 对 H 值的最大可能值很感兴趣,你能帮助他计算 吗?注意,蚂蚁爬行的路径长度可能是无穷的。
输入输出格式
输入格式:
每一行中两个数之间用一个空格隔开。
输入文件第一行包含两个正整数 n, m,分别表示 G 中顶点的个数和边的条 数。
第二行包含 n个非负实数,依次表示 n个顶点权值 w(1), w(2), …, w(n)。
第三行包含一个正整数 v0,表示给定的起点。
第四行包含一个实数 ρ,表示给定的小于 1的正常数。
接下来 m行,每行两个正整数 x, y,表示<x, y>是G的一条有向边。可能有自环,但不会有重边。
输出格式:
仅包含一个实数,即 H值的最大可能值,四舍五入到小数点后一位。
输入输出样例
说明
对于 100%的数据, n ≤ 100, m ≤ 1000, ρ ≤ 1 – 10^-6, w(i) ≤ 100 (i = 1, 2, …, n)。
因为保留一位小数,且w(i)<=100
所以当$p^k$<1e-4时可无视
也就是说,当边数大于k时就可以忽略不计
k最大为:
$log_{0.999999}1e-4$约等于$10^7$
所以用倍增floyd求最大值
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
double f[][][],w[],inf=2e18,p,ans;
int n,m,S;
int main()
{int i,j,k,t,u,v;
cin>>n>>m;
for (i=;i<=n;i++)
{
scanf("%lf",&w[i]);
}
cin>>S;
for (i=;i<=;i++)
for (j=;j<=n;j++)
for (k=;k<=n;k++)
f[i][j][k]=-inf;
for (i=;i<=n;i++)
f[][i][i]=;
scanf("%lf",&p);
for (i=;i<=m;i++)
{
scanf("%d%d",&u,&v);
f[][u][v]=p*w[v];
}
for (t=;t<=25;t++)
{
for (i=;i<=n;i++)
{
for (j=;j<=n;j++)
{
for (k=;k<=n;k++)
if (f[t-][i][k]!=-inf&&f[t-][k][j]!=-inf)
f[t][i][j]=max(f[t][i][j],f[t-][i][k]+f[t-][k][j]*p);
}
}
p=p*p;
}
ans=-inf;
for (i=;i<=n;i++)
ans=max(ans,f[][S][i]+w[S]);
printf("%.1lf\n",ans);
}
最新文章
- EF 分页查询优化
- (转)tomcat进程意外退出的问题分析
- [转载]TFS源代码管理
- SQLServer------如何删除列为NULL的行
- margin小结
- 我所了解的WEB开发(2) - PS切片
- Python学习(20)python操作mysql数据库_安装
- Linux 不挂载设备,获取设备的文件系统信息
- pygame学习资料
- oracle 解锁scott账户
- UVA 10537 - The Toll! Revisited(dijstra扩张)
- LeetCode OJ 78. Subsets
- java多线程sleep和wait方法的区别
- hexo+github创建属于自己的博客
- Convolutional Neural Network in TensorFlow
- CSS 规范 命名规则
- Python3 BP神经网络
- C#零基础入门04:打老鼠初级之枚举、重构、事件处理器
- [转帖]Cgroups 与 Systemd
- 一步一步搭建11gR2 rac+dg之DG 机器配置(七)【转】
热门文章
- 【IOS】 readonly IOS下实战入门
- linux more less cat
- iOS --转载 NSRange 和 NSString 详解
- Arcgis for Js之GeometryService实现測量距离和面积
- 修改MyEclipse内存
- JavaWeb中文乱码问题解决思路
- iOS Xcode之SVN(remove git)
- jQuery初始化$(function() { }
- Openstack块存储cinder安装配置
- curl post CURLOPT_POSTFIELDS