[Leaf] [P1073] 最优贸易

p1073-[noip-2009-提高组]-最优贸易---洛谷">P1073 [NOIP 2009 提高组] 最优贸易 - 洛谷

1. 题面梗概

中译中: 给定一个图，有一个人从 1 到 $n$ 旅游，可以在一个点买入水晶球并在随后的一个点卖出。求单次买卖的最大收益。

2. 逻辑推导

这是一个典型的路径决策问题，我们需要在路径的前面找到一个低价点买入，后面找到一个高价点卖出。

这题我有两个切入点（思路）。

2.1 双向搜索

假设我们能知道从 $1$ 到 $i$ 的所有路径中，最小的价值 $minp[i]$，以及从 $i$ 到 $n$ 的所有路径中，最大的价值 $maxp[i]$。

那么以 $i$ 为转折点的最大收益就是 $maxp[i] - minp[i]$。接着只要遍历所有路径上的点更新最值即可。

2.2 分层图

注意到有三种状态：尚未买入；持有水晶球；卖出水晶球。

因此我们可以以买入和卖出的两个点作为转折点，将图分为 $3$ 层，每层之间的边权都是 $0$。

而第一层和第二层之间的边权是 $-val[i]$，意为买入花费的钱。

第二层和第三层之间的边权是 $val[i]$，意为卖出收入的钱。

因为边权是钱，我们要收获最多的钱，如此我们在这张图上跑一遍最长路即可得到最终答案。

而因为涉及到了负权，所以 Dijkstra 死了，不过因为没有正环（可以想一想为什么），所以可以用 SPFA 跑。

3. 代码实现

▶

AcCode

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 1e5 + 50;
const ll inf = 1e18;

vector< int > adj[maxn], radj[maxn];
ll minp[maxn], maxp[maxn], val[maxn];
int n, m;

struct State {
    ll d; int u;
    bool operator < ( const State& oth ) const { return d > oth.d; }
};

void spfa_min( )
{
    for( int i = 1; i <= n; ++ i ) minp[i] = inf;
    queue< int > q;
    q.push( 1 );
    minp[1] = val[1];

    while( !q.empty( ) )
    {
        int u = q.front( ); q.pop( );

        for( int v : adj[u] )
        {
            if( minp[v] > min( minp[u], val[v] ) )
            {
                minp[v] = min( minp[u], val[v] );
                q.push( v );
            }
        }
    }
}

void spfa_max( )
{
    for( int i = 1; i <= n; ++ i ) maxp[i] = -inf;
    queue< int > q;
    q.push( n );
    maxp[n] = val[n];

    while( !q.empty( ) )
    {
        int u = q.front( ); q.pop( );

        for( int v : radj[u] )
        {
            if( maxp[v] < max( maxp[u], val[v] ) )
            {
                maxp[v] = max( maxp[u], val[v] );
                q.push( v );
            }
        }
    }
}


void solve( )
{
    cin >> n >> m;

    for( int i = 1; i <= n; ++ i ) cin >> val[i];

    for( int i = 1; i <= m; ++ i )
    {
        int x, y, z;
        cin >> x >> y >> z;
        adj[x].push_back( y );
        radj[y].push_back( x );
        if( z == 2 ) adj[y].push_back( x );
        if( z == 2 ) radj[x].push_back( y );
    }

    spfa_min( );
    spfa_max( );

    ll ans = 0;
    for( int i = 1; i <= n; ++ i )
    {
        ans = max( ans, maxp[i] - minp[i] );
    }
    cout << ans << '\n';
}

int main( )
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    solve( );
    return 0;
}

4. 复盘

• 复杂度分析：$O( kM )$。

• 碎碎念：分层图虽然是解决此类状态切换问题的万能工具，但它也可能会演变成最长路问题。在存在负权的图上，Dijkstra 对此无能为力。此时，双向维护极值反而而成了一种绕过负权的方案。

• 关联笔记：最短路体系