P5468 [NOI2019]回家路线 [斜率优化dp] 回家路线回家路线回家路线


Dis[i,j]Dis[i,j] 表示使用编号为 jj 的边走到 ii 节点的最小花费, 则

Dis[to,j]=min{Dis[ft,i]+A(pjqi)2+B(pjqi)+C}Dis[to, j]=min{Dis[ft, i] + A*(p_j-q_i)^2 + B*(p_j-q_i) + C}

使用类似 SpfaSpfa 的方法转移, 鉴于空间复杂度为 O(NM)O(NM) 的, 只有70pts70pts.

代码 .


时间的范围很小, 考虑以枚举时刻进行 dpdp,

F[i,j]F[i, j] 表示时刻 jj 走过 ii 边的最小花费, 时间复杂度 O(MT)O(MT), (TT 为最大时间) 能过 .
理论上不能 ACAC, 所以要优化 .

?怎么优化?
每个边 出发/到达时刻 都是确定的, 于是可以建一个 时间队列,
预先在对应时刻插入边, 枚举时间时, 到了对应时刻, 再将边取出参加转移.
省掉第二维.

则设 F[i]F[i] 表示 走完编号为 ii 的边的最小花费, 则
F[j]=min{F[i]+A(pjqi)2+B(pjqi)+C}F[j] = min{F[i]+A*(p_j-q_i)^2 + B*(p_j-q_i) + C}

去掉 minmin 化简, 仅关于决策的项放在一左边, 剩下的放在右边,
F[i]+Aqi2Bqi=2ApjqiF[j]Apj2BpjCF[i]+Aq_i^2-Bq_i=2Ap_jq_i-F[j]-Ap_j^2-Bp_j-C

y=kx+by = kx + b 的形式,

  • y=F[i]+Aqi2Bqiy=F[i]+Aq_i^2 - Bq_i
  • k=2Apjk=2Ap_j
  • x=qix=q_i
  • b=F[j]Apj2BpjCb = -F[j]-Ap_j^2-Bp_j-C
  1. 因为求的是最小值, 所以维护 下凸壳;
  2. 因为 kk 单调递增, 所以可以弹出队首 .

斜率优化 得到 O(M)O(M) 时间复杂度.

没学过斜率优化的可以点击 这里 .


  • 对每个点建单调队列, 所有到达该点的边都可以作为 从这条边出发的边 转移的来源,
    每条边更新后都需要加入其终点对应时刻的 候选单调队列 , 在对应时刻取出加入正式队列, 以便后面的边进行更新.

  • 注意开始时, 11 节点的单调队列需要推入 00 元素, 使得 11 出发的边得到转移 .

  • 转移时需判断决策来源是否为空, 即判断 指定边 的 出发点 的单调队列是否为空 .

转移时对每个点建单调队列保证了空间的来源正确, 遍历时间保证了时间的来源正确 .

#include<cstdio>
#include<vector>
#include<queue>
#define pb push_back
#define reg register

const int maxn = 2e5 + 10;

int N;
int M;
int A;
int B;
int C;
int Max_time;
int F[maxn];

struct Edge{ int x, y, p, q; } E[maxn];

double X(int i){ return E[i].q; }

double Y(int i){ return F[i] + A*E[i].q*E[i].q - B*E[i].q; }

double slope(int x, int y){ return (Y(x) - Y(y)) / (X(x) - X(y)); }

std::deque <int> Q[100005];

std::vector <int> Time_line[3005];
std::vector <int> Get_off[3005];

int main(){
        scanf("%d%d%d%d%d", &N, &M, &A, &B, &C);
        for(reg int i = 1; i <= M; i ++){
                scanf("%d%d%d%d", &E[i].x, &E[i].y, &E[i].p, &E[i].q);
                Max_time = std::max(Max_time, E[i].p);
                Time_line[E[i].p].pb(i);
        }
        int Ans = 0x7f7f7f7f;
        Q[1].pb(0);
        for(reg int tim = 0; tim <= Max_time; tim ++){
                int size = Get_off[tim].size();
                for(reg int j = 0; j < size; j ++){
                        int id = Get_off[tim][j];
                        int t1 = E[id].y;
                        while(Q[t1].size() >= 2 && slope(Q[t1][Q[t1].size()-1], Q[t1][Q[t1].size()-2]) >= slope(Q[t1][Q[t1].size()-2], id))
                                Q[t1].pop_back();
                        Q[t1].push_back(id);
                }
                size = Time_line[tim].size();
                for(reg int k = 0; k < size; k ++){
                        int j = Time_line[tim][k];
                        int t1 = E[j].x;
                        if(Q[t1].size() == 0) continue ;
                        double K = 2*A*E[j].p;
                        while(Q[t1].size() >= 2 && slope(Q[t1][0], Q[t1][1]) < K) Q[t1].pop_front();
                        int i = Q[t1].front();
                        F[j] = F[i] + A*(E[j].p-E[i].q)*(E[j].p-E[i].q) + B*(E[j].p - E[i].q) + C;
                        Get_off[E[j].q].pb(j);
                        if(E[j].y == N) Ans = std::min(Ans, F[j]+E[j].q);
                }
        }
        printf("%d
", Ans);
        return 0;
}