题解 P7425 【[THUPC2017] 机场】
看到数据范围这么小，那么应该是个立方左右的算法。
但是我们具体不知道是什么算法，我们先来发掘一些性质：
-
在登机桥之间或摆渡车之间瞎动是没意义的，这显然。
-
不会有在摆渡车的飞机移动到登机桥，这也显然。
-
如果一个飞机从登机桥移动到摆渡车，那么一定是在登记后下一个时刻马上过去，否则会白白占用登机桥的位置。
有了这三条之后我们发现飞机可选的状态只剩下了三种：
-
一直在摆渡车。
-
一直在登机桥。
-
在登机桥登机之后下一时刻去摆渡车。
这看起来就非常费用流，我们考虑建图。
（以下
同时处理登机桥和摆渡车不好弄，我们可以先把无解判掉（这容易使用差分加一遍前缀和办到），因为飞机只可能从登机桥到摆渡车而不会返回来，所以飞机去了摆渡车那边就可以视为直接起飞，不用管这个飞机了。这样只考虑登机桥，问题变得简单一些。
首先离散化时间，对每个时间建一个点，每个飞机建一个点。相邻两个时间点连边
然后我们讨论三种状态：
-
一直在摆渡车：他根本没有停在登机桥，算完贡献直接扔了它，于是连边
(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;
}