题解 P2570 【[ZJOI2010]贪吃的老鼠】

· · 题解

这题太神仙了，必须写篇题解记录一下。

首先，一眼能看出的是需要二分保质期T。然后呢？

然后就是十分神仙的建图了。

首先，对于时间离散化是必须的。一共n块奶酪，每块有出现和消失两个时间点，故共有2n个时间点。离散化后，我们共得到2n-1块时间块。

然后，最神仙的一点来了：

我们将老鼠按照速度从大到小排序，并在最后添加一只速度为0的老鼠。之后，进行差分。

举个例子：2\ 9\ 4\ 5\xrightarrow{\text{排序并加0}}9\ 5\ 4\ 2\ 0\xrightarrow{\text{差分}}4\ 1\ 2\ 2。

这样差分有什么用呢？

题面中有如下限制：

\text{(1)在任一时刻,一只老鼠最多可以吃一块奶酪;} \text{(2)在任一时刻，一块奶酪最多被一只老鼠吃。}

为了满足如上限制，我们进行了拆点。现在我们看看拆点是如何实现如上限制的：

这段是二分的check函数。

```cpp bool che(double ip){ memset(head,-1,sizeof(head)),cnt=0,res=0,v.clear(); for(register int i=1;i<=n;i++)ae(S,i,sz[i]),v.push_back(s[i]),v.push_back(ip+t[i]); sort(v.begin(),v.end()),CC=n; for(register int i=1;i<=m;i++){ for(register int j=1;j<v.size();j++){ if(v[j]-v[j-1]<EPS)continue; CC++,ae(CC,T,(v[j]-v[j-1])*sp[i]*i); for(register int k=1;k<=n;k++)if(((double)s[k]-v[j-1])<EPS&&ip+t[k]-v[j]>-EPS)ae(k,CC,sp[i]*(v[j]-v[j-1])); } } Dinic(); return sum-res<EPS; } ``` ------------ 可以看到，我们对于每块奶酪，都从源点连来$sz$单位的流量。如果流量跑满，就意味着合法。同时，我们进行了离散化。就是这两行的内容。 ```cpp for(register int i=1;i<=n;i++)ae(S,i,sz[i]),v.push_back(s[i]),v.push_back(ip+t[i]); sort(v.begin(),v.end()),CC=n; ``` ------------ 然后，我们开始枚举老鼠（循环$i$），再枚举时间段（循环$j$）。如果相邻的两个时间点是相同的（即差$<EPS$），就跳过。 就是这三行。 ```cpp for(register int i=1;i<=m;i++){ for(register int j=1;j<v.size();j++){ if(v[j]-v[j-1]<EPS)continue; ``` ------------ 然后，我们为（在$j$时间段内的老鼠$i$）提供一个编号（$CC$），并向汇点连去$((v[j]-v[j-1])*sp[i]*i)$的流量。 奇怪，为什么是这么多呢？ 我们看一下它的含义： $(v[j]-v[j-1])$：该时间段的长度。也就是说，后面乘上的东西应该是老鼠每秒的速度，这样得到在这么长的时间段里老鼠可以吃掉多少奶酪。 我们看一下后面的东西： $sp[i]*i

这个东西的意思是，差分值乘上它的编号。

为什么是这个呢？我们观察一下差分过程。设diff为差分数组，org为原数组。

则有\Sigma diff_i*i=\Sigma org_i。

或者看图：

我们以上面举的差分例子为例：

4\ 1\ 2\ 2\xrightarrow{sp[i]*i}4\ 2\ 6\ 8

这样连的话，就可以保证前面那两条限制。这就相当于在每一横条上取走一部分。如果从竖向来看的话，就是每只老鼠工作一部分。

这样子，我们就知道了为什么要连这么多流量。

之后就比较简单了。

这段是对于时间段j的i老鼠，我们枚举每块奶酪，如果这块奶酪存在的时间包含了这块奶酪，则连边，连的是这段时间里，这只老鼠最多能在一块奶酪上付出的努力，即(sp[i]*(v[j]-v[j-1]))。

就是这段代码：

for(register int k=1;k<=n;k++)if(((double)s[k]-v[j-1])<EPS&&ip+t[k]-v[j]>-EPS)ae(k,CC,sp[i]*(v[j]-v[j-1]));

然后，最恶心的check函数部分就讲完了。我们最后再梳理一下过程：

1.差分老鼠速度

2.开始二分

2.1.离散化时间点，求出时间段，并由源点连来（奶酪大小）单位的流量
2.2.求出某时间段的某老鼠最多可以贡献多少流量，并向汇点连这么多的流量
2.3.求出所有包含这一时间段的奶酪，并连向该老鼠
2.4.求最大流

以上就是这道神仙又巧妙的题的全过程。希望对你有帮助。

来都来了，点个赞呗~~~

附:注意网络流要写实数网络流，而非整数网络流。

代码：

#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
const double EPS=1e-7;
int TT,n,m,sz[50],s[50],t[50],sp[50],sum,CC;
namespace MaxFlow{
    const int N=10000,M=200000;
    int head[N],cur[N],dep[N],cnt,S,T;
    double res;
    struct node{
        int to,next;
        double val;
    }edge[M];
    inline void ae(int u,int v,double w){
        edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].val=w,head[u]=cnt++;
        edge[cnt].next=head[v],edge[cnt].to=u,edge[cnt].val=0,head[v]=cnt++;
    }
    queue<int>q;
    inline bool bfs(){
        memset(dep,0,sizeof(dep)),q.push(S),dep[S]=1;
        while(!q.empty()){
            register int x=q.front();q.pop();
            for(register int i=cur[x]=head[x];i!=-1;i=edge[i].next)if(edge[i].val>EPS&&!dep[edge[i].to])dep[edge[i].to]=dep[x]+1,q.push(edge[i].to);
        }
        return dep[T]>0;
    }
    bool reach;
    inline double dfs(int x,double flow){
//      printf("%d %lf\n",x,flow);
        if(x==T){
            res+=flow;
            reach=true;
            return flow;
        }
        double used=0;
        for(register int &i=cur[x];i!=-1;i=edge[i].next){
            if(edge[i].val<EPS||dep[edge[i].to]!=dep[x]+1)continue;
            register double ff=dfs(edge[i].to,min(edge[i].val,flow-used));
            if(ff>EPS){
                edge[i].val-=ff;
                edge[i^1].val+=ff;
                used+=ff;
                if(abs(flow-used)<EPS)break;
            }
        }
        return used;
    }
    inline void Dinic(){
        while(bfs()){
            reach=true;
            while(reach)reach=false,dfs(S,1e9);
        }
    }
}
using namespace MaxFlow;
double L,R;
vector<double>v;
bool che(double ip){
    memset(head,-1,sizeof(head)),cnt=0,res=0,v.clear();
    for(register int i=1;i<=n;i++)ae(S,i,sz[i]),v.push_back(s[i]),v.push_back(ip+t[i]);
    sort(v.begin(),v.end()),CC=n;
    for(register int i=1;i<=m;i++){
        for(register int j=1;j<v.size();j++){
            if(v[j]-v[j-1]<EPS)continue;
            CC++,ae(CC,T,(v[j]-v[j-1])*sp[i]*i);
            for(register int k=1;k<=n;k++)if(((double)s[k]-v[j-1])<EPS&&ip+t[k]-v[j]>-EPS)ae(k,CC,sp[i]*(v[j]-v[j-1]));
        }
    }
    Dinic();
    return sum-res<EPS;
}
void solve(){
    while(R-L>EPS){
        double mid=(L+R)/2;
        if(che(mid))R=mid;
        else L=mid;
    }
}
int main(){
    scanf("%d",&TT);
    while(TT--){
        scanf("%d%d",&n,&m),sum=0,L=R=0,S=2*n*m+n+1,T=2*n*m+n+2;
        for(register int i=1;i<=n;i++)scanf("%d%d%d",&sz[i],&s[i],&t[i]),sum+=sz[i];
        R=sum;
        for(register int i=1;i<=m;i++)scanf("%d",&sp[i]);
        sort(sp+1,sp+m+1);
        for(register int i=m;i;i--)sp[i]-=sp[i-1];
        reverse(sp+1,sp+m+1);
//      for(int i=1;i<=m;i++)printf("%d ",sp[i]);puts("");
        solve();
        printf("%lf\n",L);
    }
    return 0;
}