当前位置：网站首页>洛谷P1073 [NOIP2009 提高组] 最优贸易（分层图+最短路）
洛谷P1073 [NOIP2009 提高组] 最优贸易（分层图+最短路）
2022-06-25 06:43:00 【mfy的1号小迷弟】
洛谷P1073 [NOIP2009 提高组] 最优贸易（分层图+最短路）
题意：
带点权的有向图，每个点的点权表示，在该点购买或者卖出水晶球的价格。求从1到n，选择在一点购买水晶球，再选择在一点卖出水晶球后的最大收益。一个点可以多次经过。
思路：
方法一：缩点+dp（拓扑排序）
方法二：分层图+最短路：
每层边权为0，连接第一层的点到第二层的点的权值为点权的负数，表示在该点购买，连接第二层的点到第三层的点的权值为点权的正数，表示在该点卖出
因为有负权，只能跑spfa
边栏推荐
- Import data into Matlab
- AttributeError: ‘Upsample‘ object has no attribute ‘recompute_ scale_ factor‘
- Invalid Navicat scheduled task
- CAN透传云网关CANIOT，CANDTU记录CAN报文远程收发CAN数据
- 【Unexpected token o in JSON at position 1出错原因及解决方法】
- CAN总线工作状况和信号质量“体检”
- 判断用户是否是第一次进入某个页面
- 力扣76题，最小覆盖字串
- Analysis and utilization of Microsoft Office Word remote command execution vulnerability (cve-2022-30190)
- DNS协议及其DNS完整的查询过程
猜你喜欢
420-二叉树的层序遍历2（429. N 叉树的层序遍历、515.在每个树行中找最大值、116.填充每个节点的下一个右侧节点指针、104.二叉树的最大深度、111.二叉树的最小深度）
深度学习系列45：图像恢复综述
Technology blog ｜ how to communicate using SSE
Tips on how to design soft and hard composite boards ~ 22021/11/22
CAN透传云网关CANIOT，CANDTU记录CAN报文远程收发CAN数据
Five causes of PCB board deformation and six solutions 2021-10-08
Find out what informatization is, and let enterprises embark on the right path of transformation and upgrading
新版USBCAN卡CAN分析仪的CAN＆CANFD综合测试分析软件LKMaster主要功能介绍
Can transparent cloud gateway caniot and candtu record can messages and send and receive can data remotely
Machine learning notes linear regression of time series
随机推荐
2265. number of nodes with statistical value equal to the average value of subtree
How to select lead-free and lead-free tin spraying for PCB? 2021-11-16
Ubuntu18下登录mysql 5.7设置root密码
What are the problems with traditional IO? Why is zero copy introduced?
产品经理专业知识50篇（四）-从问题到能力提升：AMDGF模型工具
Three Siemens fire-fighting hosts fc18 are equipped with can optical transceiver for optical fiber redundant ring network networking test
MySQL simple permission management
The fourth floor is originally the fourth floor. Let's have a look
50 pieces of professional knowledge of Product Manager (IV) - from problem to ability improvement: amdgf model tool
Import data into Matlab
【日常训练】207. 课程表
判断用户是否是第一次进入某个页面
navicat定时任务无效
年后求职找B端产品经理？差点把自己坑惨了......
Importer des données dans MATLAB
力扣76题，最小覆盖字串
How to use printf of 51 single chip microcomputer
Atlassian Confluence 远程代码执行漏洞（CVE-2022-26134漏洞分析与防护
Apache CouchDB 代码执行漏洞(CVE-2022-24706 )批量POC
1742. maximum number of small balls in the box