如果您已经学过高中数学必修1,或者赶时间,建议直接看四。
一、题意的理解
有$m$条边,每条边的安全系数都是一个百分数。要求找出一条$1\to n$的路径,使得安全系数的乘积最大。
二、乘积的处理
一个处理乘积的技巧——取对数。
对数函数是在高中数学1中讲到的,若$a^t=x$,则$\log_ax=t$。其中$a\in(0,1)\cup(1,+\infty),m,n>0$。
所以很容易看出来(书本上也给出了)对数的运算规律:
$$\because a^{\log_am}=m,a^{\log_an}=n$$$$\therefore a^{\log_am}\cdot a^{\log_an}=mn$$$$\therefore a^{\log_am+\log_an}=mn$$$$\because mn=a^{\log_amn}$$$$\therefore a^{\log_am+\log_an}=a^{\log_amn}$$$$\therefore\log_am+\log_an=\log_amn$$
而此题需要我们求出乘积最大,我们就可以对每条边取自然对数(底为$\mathrm e\approx 2.71828$,在C++中可使用函数log()
得到,定义$\ln x=\log_\mathrm ex$),得到新的边权。新边权相加就是原边权相乘取对数。
实际上这个技巧还可以应用在很大的数比大小方面。这个题并不需要。
三、最大的系数
转化为加和关系后,接下来就是求最长路了。最长路的一种不容易出错的方式是把所有边都取相反数,然后跑最短路。此时每次更新的最短路径,实际上就是原图中的最长路径的相反数。而这个题范围也比较小,可以直接floyd解决。
最后再根据定义,对数运算的逆运算是指数运算——若$a^t=x$,则$\log_ax=t$。若$\log_ax=t$,则$a^t=x$。定义域同上。
那么答案就是$\mathrm e^\text{所算出的最短路的相反数}$了。可以用C++中exp()
来计算。
四、一句话题解
每条边取对数跑最长路。
五、Code:
#include<cmath>
#include<cstdio>
#include<cstring>
double f[105][105];
int main()
{
int n,m,u,v,w;
scanf("%d",&n);
while(n)
{
scanf("%d",&m);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
f[i][j]=1e10;
for(int i=1;i<=m;++i)
{
scanf("%d%d%d",&u,&v,&w);
f[u][v]=f[v][u]=-log(w/100.0);
}
for(int k=1;k<=n;++k)
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
f[i][j]=f[i][j]<f[i][k]+f[k][j]?f[i][j]:f[i][k]+f[k][j];
printf("%.6lf percent\n",exp(-f[1][n])*100);
scanf("%d",&n);
}
return 0;
}