题解：P17002 [NWERC 2019] Disposable Switches

lailai0916 · 2026-08-31 01:02:16 · 题解

题意简述

给定一张正边权无向图。每条边长为 \ell，实际耗时为 \ell/v+c，其中公共参数满足 v>0,c\ge0。求无论参数如何选择，都不可能出现在 1 到 n 的最优路径上的结点。

解题思路

设一条路径经过 k 条边，边长之和为 L。把总耗时乘以正数 v，再令 x=cv，路径代价变为：

由于 v>0,c\ge0，参数 x 可以取任意非负实数。问题转化为：找出哪些路径能在某个 x\ge0 时使 L+kx 最小。

记 f_{k,u} 为从结点 1 出发，恰好经过 k 条边到达 u 的最小边长和。枚举最后一条边即可分层转移。每条边的长度和 x 都非负，且原边长严格为正。若路径包含环，删除该环会同时减少边数和边长和，对所有 x\ge0 都更优。因此最优路径一定是简单路径，只需计算 0\le k<n。

令：

固定边数 k 后，只有边长和等于 M_k 的路径可能最优。它对应直线：

接下来要找出所有能在某个 x\ge0 处位于下包络线上的直线。

把每条存在的直线表示为点 P_k=(k,M_k)。固定 x 时，最小化 M_k+kx 等价于用斜率为 -x 的直线从下方支撑这些点。因为 x\ge0，只需要斜率不大于零的支撑线。因此答案对应点集下凸壳上的一段。

按 k 递增扫描点。设当前凸壳末尾三点依次为 P_a,P_b,P_c。若转向量满足：

则相邻边斜率下降，P_b 位于下凸壳上方，应当删除。所有乘法使用 __int128_t，不需要浮点数。

当转向量等于零时不能删除中间点。三条直线可能只在同一个参数值同时最优，中间直线虽然只在单点达到下包络，也必须保留。

下凸壳各边斜率单调不减。最左端点对应最小边数，随着 x 足够大一定最优。对后续凸壳点 P_b，它能被斜率 -x\le0 的直线支撑，当且仅当从前驱 P_a 到它的边斜率不大于零，即：

所以从左向右保留最左端点，以及所有高度不高于凸壳前驱的点，就得到全部可能最优的边数。水平边对应 x=0，其上的全部共线点都会被保留。

最后恢复可能使用的结点。对每个可行边数 k，从状态 (k,n) 反向遍历。若无向边 (u,v) 长为 w，且满足：

那么状态 (k-1,u) 是一个合法前驱。使用显式栈遍历全部最短前驱，并让不同起点共享状态访问标记。被访问状态中的结点能够出现在某条对应边数的最短路径上，其余结点就是答案。

分层动态规划和反向状态遍历的时间复杂度为 O(nm)，凸壳为 O(n)，空间复杂度为 O(n^2+m)。

正确性证明

任意含环路径删除一个环后，边长和严格减小，边数也减小，所以对所有 x\ge0 都不会更差。故某条最优路径边数小于 n。动态规划枚举最后一条边，准确得到每个边数下的最小边长和 M_k；同边数但边长和更大的路径不可能最优。

点 P_k=(k,M_k) 在斜率为 -x 的下支撑线上，当且仅当直线 M_k+kx 在参数 x 处取得全局最小值。凸壳扫描删除且仅删除下凸性被破坏的点，并保留所有共线点，所以不会遗漏只在单个参数值最优的直线。限制 x\ge0 等价于支撑斜率不大于零，凸壳前驱边斜率判定恰好选出这一部分。由此得到的边数集合不重不漏。

对可行边数 k，反向遍历只沿动态规划取等的转移。任意到达的前驱链都构成一条边长和为 M_k 的路径，因此链上结点确实可能出现在最优路径中。反过来，任意 k 边最短路径的每个前缀都满足对应动态规划等式，整条路径都会被反向遍历访问。最终未标记结点在任何参数下都不可能属于最优路径，算法正确。

参考代码

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

using i128=__int128_t;
using ll=long long;
const int N=2005;
const int M=10005;
const ll inf=0x3f3f3f3f3f3f3f3f;
struct edge
{
    int x,y;
    ll w;
};
edge e[M];
vector<pair<int,ll>>G[N];
ll f[N][N];
bool vis[N][N],use[N];
i128 cross(int x,int y,int z,int n)
{
    return i128(y-x)*(f[z][n]-f[y][n])-i128(f[y][n]-f[x][n])*(z-y);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>e[i].x>>e[i].y>>e[i].w;
        G[e[i].x].push_back({e[i].y,e[i].w});
        G[e[i].y].push_back({e[i].x,e[i].w});
    }
    memset(f,0x3f,sizeof f);
    f[0][1]=0;
    for(int i=1;i<n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            auto [x,y,w]=e[j];
            f[i][x]=min(f[i][x],f[i-1][y]+w);
            f[i][y]=min(f[i][y],f[i-1][x]+w);
        }
    }
    vector<int>h;
    for(int i=1;i<n;i++)
    {
        if(f[i][n]>=inf/2)continue;
        while(h.size()>=2&&cross(h[h.size()-2],h.back(),i,n)<0)h.pop_back();
        h.push_back(i);
    }
    vector<pair<int,int>>st;
    if(h.size())st.push_back({h[0],n});
    for(int i=1;i<h.size();i++)
    {
        if(f[h[i]][n]<=f[h[i-1]][n])st.push_back({h[i],n});
    }
    while(st.size())
    {
        auto [k,x]=st.back();
        st.pop_back();
        if(vis[k][x])continue;
        vis[k][x]=use[x]=1;
        if(!k)continue;
        for(auto [y,w]:G[x])
        {
            if(f[k-1][y]+w==f[k][x])st.push_back({k-1,y});
        }
    }
    int cnt=0;
    for(int i=1;i<=n;i++)cnt+=!use[i];
    cout<<cnt<<'\n';
    for(int i=1;i<=n;i++)
    {
        if(!use[i])cout<<i<<' ';
    }
    cout<<'\n';
    return 0;
}