题解 SP381 【CHICAGO - 106 miles to Chicago】
wjyyy
2019-01-22 15:25:47
如果您已经学过高中数学必修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：
---
```cpp
#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;
}
```