题解

先把所有登机、离开时间离散化。对每个时间点统计有多少架飞机正在占用停机位，如果某一时刻的占用数 $> a + b$，无论如何都会爆仓，直接输出 impossible。

若在任意时刻都有不超过 $a + b$ 架飞机，则可以把“有登机桥的停机位”看成一条容量为 $a$ 的时间轴：在每相邻的两个离散时间点之间连一条容量为 $a$、费用为 $0$ 的边，单位流量沿着时间轴前进就意味着“占用了一架有登机桥的停机位”。

每架飞机抽象成一个节点，源点向“登机时间”连一条容量为 $1$ 的边，飞机节点向汇点连一条容量为 $1$ 的边，再连两条“进入飞机节点”的边：

• 若选择有登机桥的停机位，就必须沿时间轴从登机时间走到离港时间，占用掉对应时间段的容量，费用为 $0$；
• 若途中改用没有登机桥的停机位，则会产生不愉快度。题目允许在停靠期间随时切换，于是我们在登机时间 / 离港时间附近额外连若干条容量为 $1$ 的边，费用分别为乘客数以及 $\lfloor P \cdot \text{乘客数} \rfloor$，让一架飞机随时“跳出时间轴”进入自己的节点——跳出的那一刻起就相当于整个停靠过程都在没有登机桥的停机位上完成。

这样一来，每条源到汇的单位流就对应一架飞机，流量经过时间轴的边表示它占用了某个登机桥（容量受限为 $a$），跳过时间轴直接进入飞机节点则表示它被分配到没有登机桥的停机位（另一种费用）。跑一遍最小费用最大流就是题目要求的最小不愉快度。

#include<bits/stdc++.h>
using namespace std;
const int N=602;
struct edge{
	int to,next;
	long long f,c;
}e[N<<6];
int head[N],tot;
int n,m,q,s,t,T,a,b;
int px[N],ps[N],pt[N],ltmp,sum[N];
double P;
struct TMP{
	int x,id;
}tmp[N];
bool cmp(TMP x,TMP y){
	return x.x<y.x;
}
struct node{
	int v,e;
}p[N];
struct mypair{
	long long dis,id;
	bool operator<(const mypair& a)const{return dis>a.dis;}
	mypair(int d,int x){dis=d,id=x;}
};
long long dis[N],h[N];
bool vis[N];
void add(int a,int b,long long f,long long c){
	e[tot].to=b;e[tot].next=head[a];e[tot].f=f;e[tot].c=c;head[a]=tot;++tot;
	e[tot].to=a;e[tot].next=head[b];e[tot].f=0;e[tot].c=-c;head[b]=tot;++tot;
}
bool dijkstra(){
	priority_queue<mypair>q;
	for(int i=s;i<=t;++i) dis[i]=1e18;
	memset(vis,0,sizeof(vis));
	dis[s]=0;
	q.push(mypair(0,s));
	while(!q.empty()){
		int u=q.top().id;
		q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=head[u];~i;i=e[i].next){
			int v=e[i].to,nc=e[i].c+h[u]-h[v];
			if(e[i].f&&dis[v]>dis[u]+nc){
				dis[v]=dis[u]+nc;
				p[v].v=u;
				p[v].e=i;
				q.push(mypair(dis[v],v));
			}
		}
	}
	return dis[t]!=1e18;
}
void spfa(){
	queue<int>q;
	for(int i=s;i<=t;++i) h[i]=1e18;
	memset(vis,0,sizeof(vis));
	h[s]=0,vis[s]=1;
	q.push(s);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];~i;i=e[i].next){
			int v=e[i].to;
			if(e[i].f&&h[v]>h[u]+e[i].c){
				h[v]=h[u]+e[i].c;
				if(!vis[v]){
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
}
void ek(){
	spfa();
	long long minc=0;
	while(dijkstra()){
		long long minf=1e18;
		for(int i=s;i<=t;++i) h[i]+=dis[i];
		for(int i=t;i!=s;i=p[i].v) minf=min(minf,e[p[i].e].f);
		for(int i=t;i!=s;i=p[i].v){
			e[p[i].e].f-=minf;
			e[p[i].e^1].f+=minf;
		}
		minc+=minf*h[t];
	}
	cout<<minc<<"\n";
}
int main(){
	cin>>T;
	while(T--){
		cin>>n>>a>>b;
		cin>>P;
		ltmp=0;
		for(int i=1;i<=n;++i){
			cin>>px[i]>>ps[i]>>pt[i];
			tmp[++ltmp].x=ps[i];
			tmp[ltmp].id=ltmp;
			tmp[++ltmp].x=pt[i];
			tmp[ltmp].id=ltmp;
		}
		sort(tmp+1,tmp+ltmp+1,cmp);
		int pre=0,cnt=0;
		for(int i=1,x,id;i<=ltmp;++i){
			x=tmp[i].x,id=tmp[i].id;
			if(x!=pre) pre=x,++cnt;
			if(id%2) ps[id/2+1]=cnt;
			else pt[id/2]=cnt;
		}
		s=0,t=cnt+n+1;
		memset(head,-1,sizeof(head));
		for(int i=1;i<cnt;++i) add(i,i+1,a,0);
		memset(sum,0,sizeof(sum));
		for(int i=1;i<=n;++i){
			++sum[ps[i]];
			--sum[pt[i]];
			add(s,ps[i],1,0);
			add(cnt+i,t,1,0);
			add(pt[i],cnt+i,1,0);
			add(ps[i],cnt+i,1,px[i]);
			if(ps[i]!=pt[i]) add(ps[i]+1,cnt+i,1,floor(P*px[i]+1e-6));
		}
		bool flag=0;
		for(int i=1;i<=cnt;++i){
			sum[i]+=sum[i-1];
			if(sum[i]>a+b){
				flag=1;
				break;
			}
		}
		if(flag){
			cout<<"impossible\n";
			continue;
		}
		ek();
	}
	return 0;
}