题解：P16424 [IATI 2022] Lifts

lailai0916 · 2026-08-31 04:24:43 · 题解

题意简述

有 k 部初始楼层任意的电梯，需要按顺序完成 n 个请求。每个请求可交给任意电梯。求所有电梯空载移动距离之和的最小值。

解题思路

一部电梯负责的请求编号必然递增。若它在完成请求 j 后继续完成请求 i，其中 j<i，则空载代价为：

把请求分给电梯，相当于把 n 个请求划分为 k 条编号递增的路径。路径中的每对相邻请求贡献一次空载代价。初始楼层可以任意选择，所以每条路径的第一个请求没有代价。

考虑一张二分图。左部点 i 表示请求 i+1 选择前驱。右部点 j 表示请求 j 成为某个后继的前驱。只在 j\le i 时连边，费用为：

匹配中的每条边连接同一部电梯连续完成的两个请求。左右两侧的匹配限制保证每个请求至多有一个前驱和一个后继。边只从较晚请求指向较早请求，因此不会形成环。

大小为 n-k 的匹配会把所有请求分成 k 条路径。反过来，任意合法划分也会产生这样的匹配。于是，原问题等价于求大小为 n-k 的最小费用匹配。

这张三角形二分图存在唯一的大小为 n-1 的匹配。左部点 1 只能选择右部点 1；删除它们后，其余点也依次被强制匹配。因此，初始匹配就是所有对角边 (i,i)，费用为：

目标匹配比初始匹配少 k-1 条边。可以从初始匹配的残量关系出发，求出撤销这些边所需的最小费用变化。

为每条对角边建立一个容量为 1 的结点 i。经过该结点表示撤销边 (i,i)，费用为：

若撤销结点 i 后改用边 (i,j)，则必须满足 j<i，并增加费用：

因此，从结点 i 向结点 j 建立相应转移。源点可以进入任意结点，任意结点也可以走向汇点。

一条流路径若经过 q 个结点，就会撤销 q 条对角边。路径同时加入 q-1 条非对角边，所以匹配大小恰好减少 1。

发送 k-1 单位流后，所有容量为 1 的结点保证这些交替路径互不冲突。最小费用流的费用就是目标匹配相对 C 的最小变化量。

直接建立转移仍需二次空间。下面按结点编号分治区间 [l,r]。设中点为 mid，本层只处理 i\in[mid+1,r]、j\in[l,mid] 的转移。其余转移分别递归到左右区间。任意 j<i 都会在两者首次分居左右区间时被唯一处理。

记：

先处理 y_j\le x_i。把左半区间的 j 按 y_j 递增排序，并为它们建立一条前缀链。第 q 个链结点连向对应的请求结点，费用为 -y_j；它还以零费用连向前一个链结点。

右半区间的 i 同样按 x_i 排序。它只需以费用 x_i 连向最后一个满足 y_j\le x_i 的链结点。沿链可以到达任意合法的 j，总费用为：

再把两类坐标同时取负，重复相同构造。此时覆盖的正是 y_j>x_i，两段费用之和为 y_j-x_i。相等情况只放进第一条链，故每条转移恰好出现一次。

每层分治的结点和边数均为 O(n)，总网络规模为 O(n\log n)。所有正向转移都会令请求编号减小，所以初始网络是有向无环图。即使网络含有负费用边，也能按拓扑序在线性时间内求出初始最短路势能。

得到势能后，所有剩余边的约化费用非负。随后用 Dijkstra 增广 k-1 次，并在每次增广后更新势能。最终答案为初始费用 C 加上最小费用流费用。

时间复杂度为 O(kn\log^2 n)，空间复杂度为 O(n\log n)。

正确性证明

首先证明匹配模型正确。每部电梯的相邻请求对应一条匹配边。一个请求至多有一个前驱和一个后继，所以这些边两两不冲突。反向边的请求编号严格减小，匹配不可能形成环。因此，大小为 n-k 的匹配与 k 条请求路径一一对应，费用也逐边相同。

再证明退流网络正确。初始匹配由所有对角边组成，费用为 C。任意目标匹配与它的对称差只能分解为交替路径，因为编号严格下降时不存在交替环。

每条路径撤销的对角边数比加入的非对角边数多 1，恰好对应一单位流。结点容量保证不同路径不会重复使用同一条对角边。因此，k-1 单位流准确表示所有大小为 n-k 的匹配。路径费用就是相对 C 的变化量。

最后证明分治压图正确。任取转移 (i,j)，其中 j<i。分治树上存在唯一一层，使 i 首次进入右半区间、j 首次进入左半区间。若 y_j\le x_i，第一条前缀链允许 i 到达 j，费用为 x_i-y_j；否则第二条链允许这次转移，费用为 y_j-x_i。两者都等于 |x_i-y_j|。其他分治层不会再次同时处理这对下标，所以压缩网络与完整转移图完全等价。

原问题、固定大小匹配、退流网络和压缩网络依次保持可行方案与费用。故算法输出的结果就是最小空载距离。

参考代码

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

using ll=long long;
const int N=10005;
const int V=200005;
const int M=1100005;
const ll inf=0x3f3f3f3f3f3f3f3f;
struct Edge
{
    int v,nxt,cap,cost;
}e[M];
int a[N],b[N],x[N],y[N],in[N],out[N];
int head[V],pos[V],pre[V],hp[V];
ll dis[V],h[V];
int s,t,tot,cnt=1,siz;
void add(int u,int v,int cap,int cost)
{
    e[++cnt]={v,head[u],cap,cost};
    head[u]=cnt;
    e[++cnt]={u,head[v],0,-cost};
    head[v]=cnt;
}
void link(int l,int mid,int r,int d)
{
    vector<int> u,v;
    for(int i=mid+1;i<=r;i++)u.push_back(i);
    for(int i=l;i<=mid;i++)v.push_back(i);
    sort(u.begin(),u.end(),[&](int i,int j){return d*x[i]<d*x[j];});
    sort(v.begin(),v.end(),[&](int i,int j){return d*y[i]<d*y[j];});
    vector<int> w(v.size());
    for(int i=0;i<v.size();i++)
    {
        w[i]=++tot;
        if(i)add(w[i],w[i-1],N,0);
        add(w[i],in[v[i]],N,-d*y[v[i]]);
    }
    int j=0;
    for(auto i:u)
    {
        while(j<v.size()&&(d*y[v[j]]<d*x[i]||(d==1&&y[v[j]]==x[i])))j++;
        if(j)add(out[i],w[j-1],N,d*x[i]);
    }
}
void build(int l,int r)
{
    if(l==r)return;
    int mid=(l+r)/2;
    link(l,mid,r,1);
    link(l,mid,r,-1);
    build(l,mid);
    build(mid+1,r);
}
void init()
{
    for(int i=1;i<=tot;i++)for(int j=head[i];j;j=e[j].nxt)if(e[j].cap)pos[e[j].v]++;
    int l=0,r=0;
    for(int i=1;i<=tot;i++)if(!pos[i])hp[r++]=i;
    fill(dis+1,dis+tot+1,inf);
    dis[s]=0;
    while(l<r)
    {
        int u=hp[l++];
        for(int i=head[u];i;i=e[i].nxt)
        {
            if(!e[i].cap)continue;
            if(dis[u]!=inf)dis[e[i].v]=min(dis[e[i].v],dis[u]+e[i].cost);
            if(!--pos[e[i].v])hp[r++]=e[i].v;
        }
    }
    for(int i=1;i<=tot;i++)h[i]=dis[i];
}
void push(int u)
{
    if(!pos[u])pos[u]=++siz;
    int i=pos[u];
    while(i>1)
    {
        int j=i/2;
        if(dis[hp[j]]<=dis[u])break;
        hp[i]=hp[j];
        pos[hp[i]]=i;
        i=j;
    }
    hp[i]=u;
    pos[u]=i;
}
int pop()
{
    int res=hp[1];
    pos[res]=-1;
    if(--siz)
    {
        int u=hp[siz+1],i=1;
        while(i*2<=siz)
        {
            int j=i*2;
            if(j<siz&&dis[hp[j+1]]<dis[hp[j]])j++;
            if(dis[hp[j]]>=dis[u])break;
            hp[i]=hp[j];
            pos[hp[i]]=i;
            i=j;
        }
        hp[i]=u;
        pos[u]=i;
    }
    return res;
}
ll flow(int k)
{
    ll res=0;
    for(int j=1;j<k;j++)
    {
        fill(dis+1,dis+tot+1,inf);
        fill(pos+1,pos+tot+1,0);
        dis[s]=0;
        siz=0;
        push(s);
        while(siz)
        {
            int u=pop();
            for(int i=head[u];i;i=e[i].nxt)
            {
                int v=e[i].v;
                if(!e[i].cap||pos[v]==-1)continue;
                ll w=(ll)e[i].cost+h[u]-h[v];
                if(dis[v]>dis[u]+w)
                {
                    dis[v]=dis[u]+w;
                    pre[v]=i;
                    push(v);
                }
            }
        }
        for(int i=1;i<=tot;i++)if(dis[i]!=inf)h[i]+=dis[i];
        int u=t;
        while(u!=s)
        {
            res+=e[pre[u]].cost;
            e[pre[u]].cap--;
            e[pre[u]^1].cap++;
            u=e[pre[u]^1].v;
        }
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i]>>b[i];
    ll ans=0;
    for(int i=1;i<n;i++)ans+=abs(a[i+1]-b[i]);
    if(k==1){cout<<ans<<'\n';return 0;}
    s=++tot;
    t=++tot;
    for(int i=1;i<n;i++)
    {
        x[i]=a[i+1];
        y[i]=b[i];
        in[i]=++tot;
        out[i]=++tot;
        add(s,in[i],1,0);
        add(in[i],out[i],1,-abs(x[i]-y[i]));
        add(out[i],t,1,0);
    }
    build(1,n-1);
    init();
    cout<<ans+flow(k)<<'\n';
    return 0;
}