自动搬运

查看原文

来自洛谷，原作者为

	绝顶我为峰 蓝的盆。

搬运于2025-08-24 22:29:45，当前版本为作者最后更新于2021-08-03 20:33:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

看到数据范围这么小，那么应该是个立方左右的算法。

但是我们具体不知道是什么算法，我们先来发掘一些性质：

• 在登机桥之间或摆渡车之间瞎动是没意义的，这显然。

• 不会有在摆渡车的飞机移动到登机桥，这也显然。

• 如果一个飞机从登机桥移动到摆渡车，那么一定是在登记后下一个时刻马上过去，否则会白白占用登机桥的位置。

有了这三条之后我们发现飞机可选的状态只剩下了三种：

• 一直在摆渡车。

• 一直在登机桥。

• 在登机桥登机之后下一时刻去摆渡车。

这看起来就非常费用流，我们考虑建图。

（以下 $i$ 表示时间点，$i'$ 表示飞机点。）

同时处理登机桥和摆渡车不好弄，我们可以先把无解判掉（这容易使用差分加一遍前缀和办到），因为飞机只可能从登机桥到摆渡车而不会返回来，所以飞机去了摆渡车那边就可以视为直接起飞，不用管这个飞机了。这样只考虑登机桥，问题变得简单一些。

首先离散化时间，对每个时间建一个点，每个飞机建一个点。相邻两个时间点连边 $(i,i+1,a,0)$ 表示飞机停在这里（登机桥最多只能停 $a$ 架飞机）；对于每个飞机，连边 $(i',T,1,0)$ 表示飞机起飞，$(S,s,1,0)$ 表示 $s$ 时这个飞机到达。

然后我们讨论三种状态：

• 一直在摆渡车：他根本没有停在登机桥，算完贡献直接扔了它，于是连边 $(s,i',1,x)$。

• 一直在登机桥：飞机需要一直等到起飞的时刻才离开登机桥，但是没有贡献，连边 $(t,i',1,0)$。

• 在登机桥登机之后下一时刻去摆渡车：在 $s+1$ 时刻以后飞机就不在登机桥了，我们让他等待一时刻，然后直接扔了它，连边 $(s+1,i',1,px)$。

然后跑费用流，就做完了。

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
struct edge
{
    int nxt,to,weight,val;
}e[100001<<2];
int T,n,m,p,tot=1,h[100001],s,t,cur[100001],dep[100001],cost,node[100001],cnt,plane[100001][3],sum[100001];
double P;
bool vis[100001];
inline int read()
{
    int x=0;
    char c=getchar();
    while(c<'0'||c>'9')
        c=getchar();
    while(c>='0'&&c<='9')
    {
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x;
}
inline void add(int x,int y,int w,int val)
{
    e[++tot].nxt=h[x];
    h[x]=tot;
    e[tot].to=y;
    e[tot].weight=w;
    e[tot].val=val;
}
inline bool SPFA()
{
    for(register int i=0;i<=t;++i)
    {
        vis[i]=0;
        dep[i]=0x3f3f3f3f;
        cur[i]=h[i];
    }
    queue<int> q;
    q.push(s);
    dep[s]=0;
    while(!q.empty())
    {
        int k=q.front();
        q.pop();
        vis[k]=0;
        for(register int i=h[k];i;i=e[i].nxt)
            if(e[i].weight&&dep[e[i].to]>dep[k]+e[i].val)
            {
                dep[e[i].to]=dep[k]+e[i].val;
                if(!vis[e[i].to])
                {
                    vis[e[i].to]=1;
                    q.push(e[i].to);
                }
            }
    }
    return dep[t]^dep[0];
}
int dfs(int k,int f)
{
    if(k==t)
    {
        vis[t]=1;
        return f;
    }
    vis[k]=1;
    int r=0,used=0;
    for(register int i=cur[k];i;i=e[i].nxt)
    {
        cur[k]=i;
        if((!vis[e[i].to]||vis[e[i].to]==t)&&e[i].weight&&dep[e[i].to]==dep[k]+e[i].val)
            if((r=dfs(e[i].to,min(e[i].weight,f-used))))
            {
                e[i].weight-=r;
                e[i^1].weight+=r;
                used+=r;
                cost+=r*e[i].val;
                if(f==used)
                    break;
            }
    }
    return used;
}
inline int dinic()
{
    while(SPFA())
    {
        vis[t]=1;
        while(vis[t])
        {
            memset(vis,0,sizeof vis);
            dfs(s,1<<20);
        }
    }
    return cost;
}
int main()
{
    T=read();
    while(T--)
    {
        tot=1;
        memset(e,0,sizeof e);
        memset(h,0,sizeof h);
        memset(node,0,sizeof node);
        memset(sum,0,sizeof sum);
        cost=0;
        n=read(),m=read(),p=read();
        scanf("%lf",&P);
        for(register int i=1;i<=n;++i)
            plane[i][0]=read(),node[++cnt]=plane[i][1]=read(),node[++cnt]=plane[i][2]=read();
        sort(node+1,node+cnt+1);
        cnt=unique(node+1,node+cnt+1)-node-1;
        s=n+cnt+1,t=s+1;
        for(register int i=1;i<cnt;++i)
        {
            add(i,i+1,m,0);
            add(i+1,i,0,0);
        }
        for(register int i=1;i<=n;++i)
        {
            plane[i][1]=lower_bound(node+1,node+cnt+1,plane[i][1])-node;
            plane[i][2]=lower_bound(node+1,node+cnt+1,plane[i][2])-node;
            ++sum[plane[i][1]];
            --sum[plane[i][2]];
            add(s,plane[i][1],1,0);
            add(plane[i][1],s,0,0);
            add(i+cnt,t,1,0);
            add(t,i+cnt,0,0);
            add(plane[i][2],i+cnt,1,0);
            add(i+cnt,plane[i][2],0,0);
            add(plane[i][1],i+cnt,1,plane[i][0]);
            add(i+cnt,plane[i][1],0,-plane[i][0]);
            add(plane[i][1]+1,i+cnt,1,(int)floor(plane[i][0]*P+1e-5));
            add(i+cnt,plane[i][1]+1,0,(int)-floor(plane[i][0]*P+1e-5));
        }
        bool flag=1;
        for(register int i=1;i<=cnt;++i)
        {
            sum[i]+=sum[i-1];
            if(sum[i]>m+p)
            {
                puts("impossible");
                flag=0;
                break;
            }
        }
        if(!flag)
            continue;
        printf("%d\n",dinic());
    }
    return 0;
}