题目分析

二分答案，然后把时间按照奶酪出现和消失的顺序离散一下，割成一段一段的，假设第 $i$段的长度为 $t _ i$。

假设没有那个一个奶酪不能同时被两只老鼠啃的限制，建图就这么建：每个奶酪建一个点，源点向其连一条流量为奶酪大小的边，每个 $i$时间段的老鼠 $j$建一个点，$i$时间段存在的奶酪向其连一条流量为 $inf$的边，这个点向汇点连一条流量为 $t _ i v _ j$的边，若所有奶酪点与源点的边均满流则有解。

那有这个限制怎么办呢？设某一块奶酪被老鼠 $i$啃了 $e_i$时间，则这个时间段奶酪被啃的总体积为：

$$S=\sum_{i=1}^m e _ i v _ i = \sum_{i=1}^m e _ i \sum_{j=1}^i v _ j- v _ {j-1}=\sum _ {j=1} ^ m (v _ j- v _ {j-1})(\sum _ {i=j} ^ m e _ i)$$

将所有老鼠按照从大到小的顺序排序，然后将第 $i$只的速度改为 $v _ i-v _ {i+1}$。若这段时间里，让第 $i$只老鼠吃 1 个时间的奶酪，则第 $i+1$到 $m$只老鼠也应吃 1 个时间的奶酪（根据上式构造实际的方案，出现不合法情况，如负数时间，一定不是最优方案），所以第 $i$只老鼠这段时间吃的奶酪上限变为 $tv _ i i$（连到汇点的边的容量）

由于奶酪这段时间被吃的总时间不能超过 $t$，所以它向每个这段时间的老鼠点连边的流量都是 $t v _ i$

然后就奥妙重重地做完了。

代码

#include<bits/stdc++.h>
using namespace std;
#define RI register int
typedef double db;
const db eps=1e-9,inf=1e14;
const int N=2005,M=1000005;
int kas,n,m,S,T,tot;db sumsz;
int sz[32],L[32],R[32],v[32];db b[62];
int h[N],kh[N],lev[N],q[N],ne[M],to[M];db flow[M];

void add(int x,int y,db z) {
    to[++tot]=y,ne[tot]=h[x],h[x]=tot,flow[tot]=z;
    to[++tot]=x,ne[tot]=h[y],h[y]=tot,flow[tot]=0;
}
db dfs(int x,db liu) {
    if(x==T) return liu;
    db sum=0;
    for(RI i=kh[x];i;kh[x]=ne[i],i=kh[x])
        if(flow[i]>eps&&lev[to[i]]==lev[x]+1) {
            db kl=dfs(to[i],min(liu-sum,flow[i]));
            flow[i]-=kl,flow[i^1]+=kl,sum+=kl;
            if(fabs(liu-sum)<eps) return sum;
        }
    lev[x]=-1;return sum;
}
int bfs() {
    for(RI i=1;i<=T;++i) lev[i]=0;
    int he=1,ta=1;lev[S]=1,q[1]=S;
    while(he<=ta) {
        int x=q[he];++he;
        if(x==T) return 1;
        for(RI i=h[x];i;i=ne[i])
            if(flow[i]>eps&&!lev[to[i]])
                lev[to[i]]=lev[x]+1,q[++ta]=to[i];
    }
    return 0;
}
db dinic() {
    db re=0;
    while(bfs()) {
        for(RI i=1;i<=T;++i) kh[i]=h[i];
        re+=dfs(S,inf);
    }
    return re;
}

int check(db tim) {
    S=n+n*m*2+1,T=n+n*m*2+2;
    tot=1;for(RI i=1;i<=T;++i) h[i]=0;
    for(RI i=1;i<=n;++i) add(S,i,sz[i]),b[i]=L[i],b[i+n]=R[i]+tim;
    sort(b+1,b+1+n+n);
    for(RI i=2;i<=n+n;++i) {
        db t=b[i]-b[i-1];
        if(t<eps) continue;
        for(RI j=1;j<=m;++j) {
            int kl=n+(i-1)*m+j;
            add(kl,T,j*v[j]*t);
            for(RI k=1;k<=n;++k)
                if(L[k]+eps<b[i]&&R[k]+tim>b[i-1]+eps) add(k,kl,v[j]*t);
        }
    }
    return fabs(sumsz-dinic())<eps;
}
bool cmp(int x,int y) {return x>y;}
int main()
{
    scanf("%d",&kas);
    while(kas--) {
        scanf("%d%d",&n,&m);sumsz=0;
        for(RI i=1;i<=n;++i) scanf("%d%d%d",&sz[i],&L[i],&R[i]),sumsz+=sz[i];
        for(RI i=1;i<=m;++i) scanf("%d",&v[i]);
        sort(v+1,v+1+m,cmp);
        db l=0,r=sumsz/v[1];
        for(RI i=1;i<m;++i) v[i]=v[i]-v[i+1];
        while(r-l>1e-5) {
            db mid=(l+r)/2.0;
            if(check(mid)) r=mid;
            else l=mid;
        }
        printf("%.5lf\n",l);
    }
    return 0;
}