题解 P1576 【最小花费】

xkzxkzxkz · 2018-08-13 00:54:57 · 题解

分析：

在n个人中，某些人的银行账号之间可以互相转账。这些人之间转账的手续费各不相同。给定这些人之间转账时需要从转账金额里扣除百分之几的手续费，请问A最少需要多少钱使得转账后B收到100元。

设扣A最少需要a元钱，经过p1,p2...pn扣除手续费w1%,w2%...wn%，那么剩下r=a(1-w1%)(1-w2%)...(1-wn%)元,由题意r=100，即

a=100/(1-w1%)(1-w2%)...(1-wn%)

因此我们需要使分子部分尽可能大，即可取得a的最小值。结合题意，可求出以1-w%作为权值的图上的最长路径。因此，我的想法是可以对Dijkstra算法或者Floyd稍作改动完成这个操作。由于Floyd算法时间复杂度比较高，经过尝试无法完成，故采用改动后的堆优化的Dijkstra算法。

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstdint>
#include <queue>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <array>

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
using std::sort;
using std::priority_queue;
using std::pair;
using std::array;
using std::make_pair;
using std::max;

#define DIJSTRA
//#define FLOYD

#ifdef DIJSTRA
struct edge
{
    int v;
    double w;

    edge(int _v, double _w)
    {
        v = _v;
        w = _w;
    }

    bool operator<(const edge &e)const
    {
        return this->w < e.w;
    }
};

const size_t data_size= 2010;
vector<edge> graph[data_size];
double costs[data_size];
bool visited[data_size];

void calc_largest(int s)
{
    memset(costs, -0x3f, sizeof(costs));
    memset(visited, false, sizeof(visited));
    costs[s] = 1;

    priority_queue<edge> q;
    q.push(edge(s, 1));
    while (!q.empty())
    {
        edge top = q.top(); q.pop();
        int u = top.v;

        if (visited[u])
        {
            continue;
        }

        visited[u] = true;
        for (int i = 0; i < graph[u].size(); i++)
        {
            int v = graph[u][i].v;
            double w = graph[u][i].w;
            if (!visited[v]&&costs[v] < costs[u] * w)
            {
                costs[v] = costs[u] * w;
                q.push(edge(v, costs[v]));
            }
        }
    }
}

int main(void)
{
    int n = 0, m = 0;
    cin >> n >> m;

    for (int i = 0; i < m; i++)
    {
        int x = 0, y = 0;
        double w = 0;
        cin >> x >> y >> w;
        graph[x].push_back(edge(y, 1-w/100.0));
        graph[y].push_back(edge(x, 1-w/100.0));
    }

    int a = 0, b = 0;
    cin >> a >> b;
    calc_largest(a);

    double largest_cost = costs[b];

    cout << std::fixed << std::setprecision(8) << (double(100) / double(largest_cost)) << endl;

    return 0;
}
#endif

#ifdef FLOYD

array<array<double, 2010>, 2010> costs;

int main()
{
    int n = 0, m = 0;
    cin >> n >> m;
    for (int i = 0; i <= n + 1; i++)
    {
        costs[i].fill(1);
    }

    for (int i = 0; i < m; i++)
    {
        int u = 0, v = 0;
        double w = 0;
        cin >> u >> v >> w;
        w = 1.0 - w / 100.0;
        costs[u][v] = costs[v][u] = w;
    }

    for (int k = 1; k <= n; k++)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                costs[i][j] = max(costs[i][j], costs[i][k] * costs[k][j]);
            }
        }
    }

    int a = 0, b = 0;
    cin >> a >> b;
    double lowest = costs[a][b];
    cout << std::fixed << std::setprecision(8) << double(100) / lowest << endl;
    return 0;
}

#endif