题解 首先看到我们是要求的是最小的可以让我们吃完的T TT，显然这是单调可以二分的。 那我们要考虑如何判断我们在延长m i d midmid的情况下是否能够得到一个合法解。 这东西呢，我们可以考虑用网络流求解。 但注意，原问题有要求一只老鼠每个时刻只能吃一块蛋糕，一块蛋糕也只能被一只老鼠吃，这个问题不太好解决。 关于第一个限制，我们可以按时间段拆点，每个时间段给一只老鼠连固定流量的边，保证每只老鼠最多使用这么多流量，一次保证它最多只会吃一块蛋糕。 但第二个条件咋搞？限制蛋糕单位时间总流量？每只老鼠吃的速度不同呀。 事实上我们可以利用差分解决这个问题。 我们先将所有老鼠吃的速度从小到大排序，然后差分，第i ii个差分段能够对应到第i ii只到第n nn只老鼠，所以流入的总流量就是n − i + 1 n-i+1n−i+1乘上差分段的长度，它向蛋糕单位时间则只会流差分段长度的流量。 我们很容易将这个图映射回每只老鼠的吃法，也一定满足上面的条件，每块蛋糕被吃的总量不会超过最大值，每只老鼠也不会超过它能从的总量。 但是是否是在我们这个单位时间内吃的就很难说了。 不过可以证明一定是可以映射到一组合法解上的。 就按这样跑一遍网络流，判断是否满流即可。

时间复杂度O ( [ 网 络 流 ] log ⁡ T )

#include<bits/stdc++.h>
using namespace std;
#define MAXN 2005  // 最大节点数
#define lowbit(x) (x&-x)  // 树状数组操作
#define reg register  // 寄存器优化
#define pb push_back  // 向量添加元素
#define mkpr make_pair  // 创建键值对
#define fir first  // 键值对的第一个元素
#define sec second  // 键值对的第二个元素
#define lson (rt<<1)  // 线段树左子节点
#define rson (rt<<1|1)  // 线段树右子节点
typedef long long LL;
typedef unsigned long long uLL; 
typedef long double Ld;
typedef pair<LL,int> pii;
const int INF=0x3f3f3f3f;  // 无穷大
const int mo=19930726;  // 模数
const int mod=1e6+7;  // 模数
const int inv2=499122177;  // 2的逆元
const int inv3=332748118;  // 3的逆元
const int jzm=2333;  // 常数
const int zero=2000;  // 偏移量
const int n1=100;  // 常数
const int orG=3,ivG=332748118;  // NTT相关
const double Pi=acos(-1.0);  // 圆周率
const double feps=1e-11;  // 浮点精度
const double eps=1e-9;  // 浮点精度
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}  // 绝对值
template<typename _T>
void read(_T &x){  // 快读
    _T f=1;x=0;char s=getchar();
    while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
    while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}
    x*=f;
}
template<typename _T>
void print(_T x){if(x<0)putchar('-'),print(-x);if(x>9)print(x/10);putchar(x%10+'0');}  // 快写
int gcd(int a,int b){return !b?a:gcd(b,a%b);}  // 最大公约数
int add(int x,int y,int p){return x+y<p?x+y:x+y-p;}  // 模加法
void Add(int &x,int y,int p){x=add(x,y,p);}  // 模加法
int qkpow(int a,int s,int p){int t=1;while(s){if(s&1)t=1ll*t*a%p;a=1ll*a*a%p;s>>=1;}return t;}  // 快速幂
int TT,n,m,s[35],totb,cnt,S,T,head[MAXN],tot,dis[MAXN],cur[MAXN];
double b[65];queue<int>q;  // 队列用于BFS
struct ming{int p;double r,d;}a[35];  // 奶酪结构体
struct edge{int to,nxt;double flow;int op;}e[MAXN*20];  // 网络流边结构
void addEdge(int u,int v,double f){e[++tot]=(edge){v,head[u],f,0};head[u]=tot;}  // 添加边
void addedge(int u,int v,double f){  // 添加双向边（网络流）
    addEdge(u,v,f);e[tot].op=tot+1;
    addEdge(v,u,0);e[tot].op=tot-1; 
}
bool bfs(){  // BFS构建分层图
    for(int i=1;i<=cnt;i++)cur[i]=head[i],dis[i]=0;
    while(!q.empty())q.pop();dis[S]=1;q.push(S);
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].to;if(e[i].flow<eps||dis[v])continue;
            dis[v]=dis[u]+1;q.push(v);
            if(v==T)return 1;  // 到达汇点
        }
    }
    return 0;
}
double dfs(int u,double maxf){  // DFS找增广路
    if(u==T)return maxf;double res=0;
    for(int i=cur[u];i;cur[u]=i=e[i].nxt){
        int v=e[i].to;if(e[i].flow<eps||dis[v]!=dis[u]+1)continue;
        double tmp=dfs(v,min(maxf,e[i].flow));  // 递归
        maxf-=tmp;res+=tmp;e[i].flow-=tmp;e[e[i].op].flow+=tmp;  // 更新流量
        if(maxf<eps)break;  // 流量用尽
    }
    return res;
}
double dinic(){double res=0;while(bfs())res+=dfs(S,1e9);return res;}  // Dinic算法

// 检查给定D是否可行
bool check(double mid){
    totb=0;
    // 1. 离散化时间点：收集所有奶酪的出现和消失时间
    for(int i=1;i<=n;i++)b[++totb]=a[i].r,b[++totb]=a[i].d+mid;
    sort(b+1,b+totb+1);  // 排序
    totb=unique(b+1,b+totb+1)-b-1;  // 去重，得到totb个时间点

    // 2. 初始化网络流节点
    cnt=totb*m+n;  // 总节点数：时间区间节点(totb-1)*m + 奶酪节点n
    S=++cnt; T=++cnt;  // 源点S和汇点T
    double summ=0;  // 所有奶酪的总重量

    // 3. 初始化图
    for(int i=1;i<=cnt;i++)head[i]=0;tot=0;

    // 4. 添加边：
    //    a. 奶酪节点 -> 汇点：容量为奶酪重量
    for(int i=1;i<=n;i++)addedge(i,T,1.0*a[i].p),summ+=a[i].p;

    //    b. 源点 -> 时间区间节点：容量为 (m-j+1)*(速度差)*(区间长度)
    for(int i=1;i<=totb;i++)  // i是离散化后的时间点下标
        for(int j=1;j<=m;j++){  // j是老鼠洞速度等级
            // 计算区间长度
            double interval = b[i]-b[i-1];
            // 速度差：s[j]-s[j-1]（s[0]默认为0）
            double speedDiff = s[j]-s[j-1];
            // 容量 = (m-j+1) * 速度差 * 区间长度
            double capacity = 1.0*(m-j+1)*speedDiff*interval;
            // 添加源点到区间等级节点的边
            addedge(S,n+(i-1)*m+j,capacity);
            
            //    c. 时间区间节点 -> 奶酪节点：若奶酪覆盖该区间，则连边（容量无穷）
            for(int k=1;k<=n;k++)  // 遍历奶酪
                // 检查奶酪k是否覆盖当前区间[b[i-1], b[i]]
                if(a[k].r<=b[i-1]+eps && a[k].d+mid+eps>=b[i])
                    addedge(n+(i-1)*m+j,k,1e9);  // 容量设为极大值
        }

    // 5. 计算最大流
    double tmp=dinic();
    // 判断：最大流是否 >= 总重量（考虑浮点误差）
    return tmp+eps>=summ; 
}
int main(){
    read(TT);  // 读入测试用例数
    while(TT--){
        read(n);read(m);  // 读入奶酪数和老鼠洞数
        for(int i=1;i<=n;i++)scanf("%d %lf %lf",&a[i].p,&a[i].r,&a[i].d);  // 读入奶酪属性
        for(int i=1;i<=m;i++)read(s[i]);  // 读入老鼠洞速度
        sort(s+1,s+m+1);  // 速度排序（升序）

        // 二分答案：在[0, 3000000]范围内找最小D
        double l=0,r=3000000;
        int times=50;  // 二分次数
        while(times--){
            double mid=(l+r)/2.0;
            if(check(mid))r=mid;  // 若D=mid可行，则尝试更小的D
            else l=mid;  // 否则尝试更大的D
        }
        printf("%.4f\n",l);  // 输出答案
    }
    return 0;
}

关键点解释 二分答案框架：

在 [0, 3000000] 范围内二分查找最小 D。

每次二分通过 check(mid) 验证 D=mid 是否可行。

网络流建模：

源点 S：连接所有时间区间节点。

时间区间节点：

离散化时间点形成区间 [b_{i-1}, b_i]。

对每个区间和速度等级 j 建立节点，容量为 (m-j+1)(s[j]-s[j-1])(区间长度)。

奶酪节点：连接汇点 T，容量为奶酪重量。

时间区间 → 奶酪：若奶酪覆盖该区间，则连容量无穷的边。

速度分层技巧：

将老鼠洞速度升序排序。

速度差 s[j]-s[j-1] 表示新增的速度能力。

因子 (m-j+1) 表示速度≥s[j] 的老鼠洞数量。

最大流验证：

使用 Dinic 算法计算最大流。

若最大流 ≥ 奶酪总重量，则 D 可行。

为什么这样建模？ 时间区间离散化：将连续时间分割为小区间，便于处理。

速度差分：将老鼠洞能力分解，避免重复计算。

容量设计：(m-j+1)(速度差)(区间长度) 确保同一时间区间内，所有老鼠洞的总能力被精确表示。

网络流正确性：最大流等于奶酪总重量时，说明存在分配方案吃完所有奶酪。

该算法高效且精确，通过二分和网络流解决了复杂的时空分配问题。