IMA+DeepSeek撰写NOIP2009T3最优贸易解题报告

摘要：此题解幅IMA+DeepSeek依据个人知识库生成，采用分层图+SPFA策略：将每个城市拆分为三层（购买前/持有/售出），购买时从第0层转入第1层并扣除价格，售出时从1层转入2层增加价格。通过SPFA求最长路，终点的第三层距离即为最大差价。时间复杂度O(M)，空间O(M)。

liufangshun

451人浏览 · 2025-03-04 09:46:31

liufangshun · 2025-03-04 09:46:31 发布

一、提问词

你是一个具有10年以培训经验的信息奥赛教练，现请你撰写NOIP2009提高组T3最优贸易题解：
一、题解至少包括以下几个部分：
'''
1、题目描述
2、解题思路
3、实现代码
4、代码说明
'''
二、要求
'''
1、代码符合C++98规范
2、从文件“trade.in”读数据，答案写入文件“trade.out”。
'''

二、IMA+DeepSeek回复

1、题目描述

C国有n个城市和m条道路，每条道路连接两个城市，可能是单向或双向。阿龙想选择一个城市买入水晶球，并在之后某个城市卖出，最多进行一次交易。求最大可能的差价。

输入格式：
第1行：n、m（城市数和道路数）
第2行：n个整数表示各城市水晶球价格
接下来m行：x,y,z描述道路（z=1为单向，z=2为双向）

输出格式：
一个整数表示最大收益（若无交易则输出0）

2、解题思路

三步处理法

正向SPFA求最小价：从起点出发，计算每个城市可达路径的最小价格
反向SPFA求最大价：从终点出发反向建图，计算各城市可达终点的路径的最大价格
枚举求差值：遍历所有城市，计算max(当前最大卖出价 - 历史最小买入价)

方法正确性证明：任何合法路径都可以划分为1→k→n，其中k为买卖分界点。正向处理保证买入最低价，反向处理保证卖出最高价。1

3、实现代码

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=100005;

struct Edge{
    int to,next;
}e[maxn*10],re[maxn*10];  //正向边和反向边

int head[maxn],rhead[maxn];  //正向图和反向图头指针
int price[maxn],min_cost[maxn],max_value[maxn];
bool inq[maxn],vis[maxn];
int n,m,cnte;

void add_edge(int u,int v){
    //正向图邻接表
    e[++cnte].to = v;
    e[cnte].next = head[u];
    head[u] = cnte;
    
    //反向图邻接表
    re[cnte].to = u;
    re[cnte].next = rhead[v];
    rhead[v] = cnte;
}

void forward_spfa(){
    memset(min_cost,0x3f,sizeof min_cost);
    queue<int> q;
    q.push(1);
    min_cost[1] = price[1];
    inq[1] = true;

    while(!q.empty()){
        int u = q.front(); q.pop();
        inq[u] = false;
        for(int p=head[u];p;p=e[p].next){
            int v = e[p].to;
            int new_min = min(min_cost[u], price[v]);
            if(min_cost[v] > new_min){
                min_cost[v] = new_min;
                if(!inq[v]){
                    q.push(v);
                    inq[v] = true;
                }
            }
        }
    }
}

void reverse_spfa(){
    memset(max_value,-0x3f,sizeof max_value);
    queue<int> q;
    q.push(n);
    max_value[n] = price[n];
    inq[n] = true;

    while(!q.empty()){
        int u = q.front(); q.pop();
        inq[u] = false;
        for(int p=rhead[u];p;p=re[p].next){
            int v = re[p].to;
            int new_max = max(max_value[u], price[v]);
            if(max_value[v] < new_max){
                max_value[v] = new_max;
                if(!inq[v]){
                    q.push(v);
                    inq[v] = true;
                }
            }
        }
    }
}

int main(){
    freopen("trade.in","r",stdin);
    freopen("trade.out","w",stdout);

    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&price[i]);
    for(int i=1;i<=m;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add_edge(x,y);
        if(z == 2) add_edge(y,x);
    }

    forward_spfa();
    reverse_spfa();

    int ans = 0;
    for(int i=1;i<=n;i++)
        ans = max(ans, max_value[i]-min_cost[i]);
    printf("%d\n",ans);
    return 0;
}

4、代码说明

数据结构：
- 使用两个邻接表存储正向图和反向图
- min_cost[]数组记录从起点到各城市路径中最小的买入价
- max_value[]数组记录从该城市到终点路径中最大的卖出价
关键过程：
- add_edge：同时维护正向和反向邻接表，处理双向边时添加反向边
- forward_spfa：使用改进SPFA算法逐步松弛得到每个节点的最小价格
- reverse_spfa：在反向图上进行SPFA得到每个节点的最大可卖出价格
复杂度分析：
- 时间复杂度：O(M)，两个SPFA的时间复杂度均为线性
- 空间复杂度：O(N+M)，存储正向和反向图的边
算法优势：
- 避免暴力枚举所有路径
- 保证处理包含环路的复杂图结构
- 反向预处理确保卖出点可达终点