算法提高课汇总

模型抽象

• $n$个人: $n$个顶点.

• 某些人可相互转账: 无向边.

• $z\%$的手续费: 假设从$u$到$v$转账$x$元, 则$v$收到实际钱数为$x\times(1\;-\;z\%)$元. 为方便描述下面
  用$w = (1\;-\;z\%)$表示边的权值.

• $A$转账$B$到账$100$元最少需要的总费用: 假设$A$ --> $B$之间某条路径的边权为$w_1, w_2, …, w_n$.
  则$A$需要的费用$x\times w_1\times w_2\times .... \times w_n = 100$. 为使得$A$的费用最小, 即求
  $w_1\times w_2\times .... \times w_n$的最大值. 可以用单源最短路实现.

证明:

1. 题目要求路径权值乘积$w_1\times w_2\times .... \times w_n$最大, 对路径权值乘积加上$\lg$运算, 即求
   $\lg(w_1\times w_2\times .... \times w_n) = \lg(w_1) + \lg(w_2) + .... + \lg(w_n)$的最大. 题目从
   求乘积最大可转换为求权值$\lg$和的最大.

2. 由于$0\lt w_i\le 1$ --> $\lg(w_i)\lt 0$. 若在每项前加上符号使得所有项非负, 题目转换为求
   $-\lg(w_1) + -\lg(w_2) + .... + -\lg(w_n)$的最小值. 也就是对边权做$-\lg$运算处理后(可以这么
   做的原因是$\lg$函数是单调的, 不影响求最值), 题目转换为无向图求单源最短路径.

注意: 本题可以用$Dijkstra$算法解决, 是题目有$z\lt100$ --> $0\le z\%\lt 1$ --> $0\lt w\le 1$
--> $-\lg(w)\gt 0$的限制, 即在转换后边权非负.

代码实现

• 上述叙述需要用到麻烦的$\lg$函数, 但只是证明了算法的正确性. 具体实现是可以直接用权值相乘的最大值求解.

朴素$Dijkstra\;O(n^2)$

#include <iostream>

using namespace std;

const int N = 2010;

int n, m, s, t;
double w[N][N];
double dist[N];
bool st[N];

void dijkstra()
{
    //memset(dist, 0, sizeof dist);
    dist[s] = 1.0;
    for( int i = 0; i < n; i ++ )
    {
        int u = -1;
        for( int v = 1; v <= n; v ++ )
        {
            if( !st[v] && ( u == -1 || dist[v] > dist[u]) )
                u = v;
        }

        st[u] = true;
        for( int v = 1; v <= n; v ++ )
            dist[v] = max( dist[v], dist[u] * w[u][v] ); //s->v 权值乘积的最大值
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    while ( m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        double d = (100.0 - c) / 100;
        w[a][b] = w[b][a] = max( w[a][b], d );
    }
    scanf("%d%d", &s, &t);

    dijkstra();
    printf("%.8lf\n", 100 / dist[t] );

    return 0;
}