P1073

题目大意：给定一个 N 个点，M 条边（存在反向边）的有向图，点有点权，求一条从 1 到 N 的路径上，任意选出两个点 p，q (p 在前，q在后)，两点点权的差值最大。 根据最短路的 dp 思想，可以先对原图进行一次 dij...

　　题目传送门 最优贸易 题目描述 C 国有n 个大城市和m 条道路，每条道路连接这n 个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这m 条道路中有一部分为单向通行...

最优贸易 题目链接 看题解后感觉分层图好像非常NB巧妙 建三层n个点的图，每层图对应的边相连，权值为0 即从一个城市到另一个城市，不进行交易的收益为0 第一层的点连向第二层对应的点的边权为-w[i],表示买入的收...

传送门 解题思路 很长的题，实际上在一个有向图（点有点权）中求一个从起点1到终点n的路径，使得这条路径上点权最大的点与点权最小的点的差值最大（要求必须从点权较小的点能够走到点权较大的点）。 —&mda...

本题就是在一条1-n的路径上找p，q（先经过p），使得q-p最大。 考虑建正反图，正图上求出d[x]，表示1-x的路径经过的节点最小值，反图上则从n开始求出f[x]，x-n的最大值，最后枚举断点i，取最大的f[i]-d[i]就是答案...