题解：AT_agc072_e [AGC072E] Flights 2

max0810 · 2025-11-13 21:35:08 · 题解

[AGC072E] Flights 2

给定一张 n 个点 m 条边的有向图和正整数 F，每条边有边权 w_i，通过这条边需要花费 F\times w_i 元，并获得 w_i 里程。在点 i 时，你可以将 x 里程兑换为 r_ix 元（x 可以为任意正实数）。初始时你在机场 1，有 0 里程，求要到达 n 初始时至少要带多少钱。

多组数据。\sum n^2\le 160000,m\le n(n-1),r_i < F\le 100,w_i\le 100。

神仙题。

有个朴素 dp，设 f_{i,j} 表示在点 i 时，有 j 里程，要到达 n 至少需要多少钱，但是这个 dp 状态数太多了。考虑减少 dp 状态，可以思考每次我们将一些里程兑换为钱时有哪些情况。可以发现，每次兑换时，要么是将所有里程都换成钱，要么是将一些里程换为钱，并且在到达下一个兑换点时刚好将钱用完。

考虑证明，如果某次兑换既没有把里程花完，到下一个兑换点时也没有把钱花完，假设这两个点分别为 x,y，我们根据 r_x,r_y 的大小关系考虑。如果 r_x > r_y，那么在 x 时多换 \epsilon 里程，在 y 时少换 \epsilon 里程一定更优；如果 r_x\le r_y，那么在 x 时少换 \epsilon，在 y 时多换 \epsilon 一定不劣。也就说明了上述结论的正确性，那么在相邻两个兑换点之间，一定走的是边权的最短路，不然一定不优，我们可以先 \mathcal{O}(n^3) 预处理出 d_{i,j} 表示 i 走到 j 的最短路长度。

接下来我们就不用记录 j 这一维了，只需要考虑每次钱变为 0 或里程变为 0 的状态，设 f_u 表示在点 u 时里程为 0，要走到 n 至少需要多少钱，g_u 表示在点 u 时钱为 0，要走到 n 至少需要多少里程。初始化 f_n = g_n = 0，答案为 f_1，接下来考虑如果从某个兑换点 u 走到了下一个兑换点 v，应该如何更新，分四种讨论：

从 f_u 走到 f_v，那么一定是直接从 u 走到 v，并在 v 时将所有里程兑换为钱，条件为：\left\{\begin{matrix}f_u\ge d_{u,v}F \\ f_u-d_{u,v}F+d_{u,v}r_v\ge f_v\end{matrix}\right.，于是转移为 f_u\larr \max(f_v-d_{u,v}r_v,0)+d_{u,v}F。
从 f_u 走到 g_v，那么中间可能存在一个兑换点 x，先从 u 走到 x，然后在 x 处将一些里程兑换为钱，然后走到 v 时钱正好花光。可以发现中间的兑换点至多一个，要不然中间就会出现其他的里程或钱为 0 的状态。我们枚举这个 x，如果 x=u 就表示没有中间的兑换点，条件为：
\left\{ \begin{matrix}f_u\ge d_{u,x}F \\ d_{u,x}\ge \frac{d_{x,v}F-(f_u-d_{u,x}F)}{r_x} \\ d_{u,x}-\frac{d_{x,v}F-(f_u-d_{u,x}F)}{r_x}+d_{x,v} \ge g_v \end{matrix} \right.
其中 \frac{d_{x,v}F-(f_u-d_{u,x}F)}{r_x} 表示在点 x 时需要用多少里程换钱，于是转移条件为 d_{u,x}+d_{x,v}\ge g_v，转移式子为：f_u\larr \max(d_{x,v}F-\min(d_{u,x},d_{u,x}+d_{x,v}-g_v)\times r_x)+d_{u,x}F。
从 g_u 走到 g_v，那么一定是在 u 时用一些里程兑换为钱，走到 v 时钱正好花光，条件为 \left\{\begin{matrix}g_u\ge \frac{d_{u,v}F}{r_u} \\ g_u-\frac{d_{u,v}F}{r_u}+d_{u,v}\ge g_v\end{matrix}\right.，转移为 g_u\larr \max(g_v-d_{u,v},0)+\frac{d_{u,v}F}{r_u}。
从 g_u 走到 f_v，那么一定是在 u 时用一些里程兑换为钱，走到 v 时钱正好花光，然后再将所有此时的所有里程兑换为钱。可以发现前面部分就是从 g_u 走到 g_v 时做的转移，于是我们只需要处理后面部分将所有里程兑换为钱，即 g_v\larr \frac{f_v}{r_v}。

可以发现一个点不会重复经过，因为 r_i < F 所以如果从一个点走回到这个点，即使将里程都兑换了也亏钱。于是我们可以用 Bellman-Ford 算法，即重复 n 次，每次处理上述所有更新，这样复杂度是 \mathcal{O}(n^4) 的。

考虑优化，我们尝试找出一个在不断走的过程中保持单调的量，设 M 表示某一时刻的钱数，C 表示里程数，可以发现，M+C\times F 一定是不增的。于是可以用 Dijkstra，每次找出 M+C\times F 最小的状态，然后更新其他所有状态，重复 2n 次即可，总复杂度为 \mathcal{O}(n^3)。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define up(x,y) x = min(x,y)
#define ll long long
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
using namespace std;
const int N = 405;
const double eps = 1e-10;
int d[N][N],n,m;
double f[N][2],r[N],F;
bool vis[N][2];
inline double get(int i,int o){return f[i][o]*(o?F:1);}
void solve()
{
    int u = 0,tp = 0;double v = 1e18;
    for(int i = 1;i <= n;i++)for(int o : {0,1})
        if(!vis[i][o]&&get(i,o) < v)v = get(i,o),u = i,tp = o;
    vis[u][tp] = 1;v = f[u][tp];
    if(!tp)
    {
        if(r[u] > eps)up(f[u][1],v/r[u]);
        for(int i = 1;i <= n;i++)up(f[i][0],max(v-d[i][u]*r[u],0.0)+d[i][u]*F);
    }
    else for(int i = 1;i <= n;i++)
    {
        if(r[u] > eps)up(f[i][1],max(v-d[i][u],0.0)+d[i][u]*F/r[i]);
        for(int j = 1;j <= n;j++)if(d[i][j]+d[j][u] > v-eps)
            up(f[i][0],max(d[j][u]*F-min(d[i][j]*1.0,d[i][j]+d[j][u]-v)*r[j],0.0)+d[i][j]*F);
    }
}
char buf[1<<21],*p1,*p2;
inline int rd()
{          
    char c;int f = 1;
    while(!isdigit(c = getchar()))if(c=='-')f = -1;
    int x = c-'0';
    while(isdigit(c = getchar()))x = x*10+(c^48);
    return x*f;
}
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    for(int T = rd();T--;)
    {
        n = rd();m = rd();F = rd();
        for(int i = 1;i <= n;i++)for(int o : {0,1})
            f[i][o] = i==n?0:1e9,vis[i][o] = 0;
        for(int i = 1;i <= n;i++)for(int j = 1;j <= n;j++)d[i][j] = i==j?0:1e9;
        for(int i = 1;i <= m;i++)
        {int u = rd(),v = rd(),w = rd();d[u][v] = min(d[u][v],w);}
        for(int i = 1;i <= n;i++)r[i] = rd();
        for(int k = 1;k <= n;k++)for(int i = 1;i <= n;i++)for(int j = 1;j <= n;j++)
            d[i][j] = min(d[i][j],d[i][k]+d[k][j]);
        for(int t = n*2;t--;)solve();
        printf("%.10lf\n",f[1][0]);
    }
    return 0;
}