洛谷$P2570\ [ZJOI2010]$贪吃的老鼠 网络流+二分
正解:网络流+二分
解题报告:
和上一题有点儿像,,,?$QwQ$但是比上一题要有趣很多$QwQ$
首先把大致思路捋下?依然是.二分出每个奶酪的开始和结束时间,然后check下最大流的流量和$\sum p$的大小.做完了.$over$
然后详细考虑过程,发现难点就在构图了呗,就,怎么构图能满足题目给定的条件
先列出题目两个和普通网络流不同的点趴$QwQ$:
1)每个奶酪有特定的开始&结束时间
2)同一个时间段一个奶酪只能被一只老鼠吃
$umm$其实第一个条件还是相对来说比较好实现的了,就考虑把时间拆成若干个区间,每个奶酪只要指向特定的区间就好$QwQ$
但是考虑第二个条件要怎么解决?这个姿势点我记得叶佬在省选前港网络流的时候港过这个技巧,,,?就说差分之后再连边.仔细思考下发现差分之后再连边就怎么跑都只相当于是被一只老鼠吃了$QwQ$
然后注意下差分之后的老鼠点和$T$连边时候的流量嗷$QwQ$
最后总结下怎么建图$QwQ$?奶酪建一排点,老鼠和时间一块儿建一排点,连边还是挺简单的不说了$QwQ$
然后不知道为什么我$T$了6个点,,,但是我自己拍都跑得挺快的,,,要哭了$QAQ$
$upd:$
这题真的是玄学趴,,,?就,我把$double$改成$float$,想着应该会跑得快些?结果$T$了9个点????$nmdwsm$,,$QAQ$
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define lf double
#define gc getchar()
#define t(i) edge[i].to
#define n(i) edge[i].nxt
#define w(i) edge[i].wei
#define ri register int
#define rb register bool
#define rc register char
#define rp(i,x,y) for(ri i=x;i<=y;++i)
#define my(i,x,y) for(ri i=x;i>=y;--i)
#define e(i,x) for(ri i=head[x];~i;i=n(i))
const int N=200000+10;
const lf eps=1e-5,inf=1e7;
int S,T,ed_cnt=-1,head[N],cur[N],dep[N],n,m,st_cnt,s[N];
lf l,r,sum,a[N],st[N];
struct ed{int to,nxt;lf wei;}edge[N<<2];
struct node{int p,r;lf d;}nod[N];
il int read()
{
rc ch=gc;ri x=0;rb y=1;
while(ch!='-' && (ch>'9' || ch<'0'))ch=gc;
if(ch=='-')ch=gc,y=0;
while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc;
return y?x:-x;
}
il bool cmp(ri x,ri y){return x>y;}
il int name(ri x,ri y){return n+(x-1)*st_cnt+y;}
il void ad(ri x,ri y,lf z)
{edge[++ed_cnt]=(ed){x,head[y],z};head[y]=ed_cnt;edge[++ed_cnt]=(ed){y,head[x],(lf)0};head[x]=ed_cnt;}
il bool bfs()
{
queue<int>Q;Q.push(S);memset(dep,0,sizeof(dep));dep[S]=1;
while(!Q.empty())
{ri nw=Q.front();Q.pop();e(i,nw)if(w(i)-eps>0 && !dep[t(i)])dep[t(i)]=dep[nw]+1,Q.push(t(i));}
return dep[T];
}
il lf dfs(ri nw,lf flow)
{
if(nw==T || !flow)return flow;lf ret=0;
for(ri &i=cur[nw];~i;i=n(i))
if(w(i) && dep[t(i)]==dep[nw]+1)
{lf tmp=dfs(t(i),min(flow,w(i)));ret+=tmp,w(i)-=tmp;w(i^1)+=tmp,flow-=tmp;}
return ret;
}
il lf dinic(){lf ret=0;while(bfs()){rp(i,S,T)cur[i]=head[i];while(lf d=dfs(S,inf))ret+=d;}return ret;}
il bool check(lf t)
{
memset(head,-1,sizeof(head));ed_cnt=-1,st_cnt=0;memset(a,0,sizeof(a));
rp(i,1,n)nod[i].d+=t,st[++st_cnt]=nod[i].r,st[++st_cnt]=nod[i].d;
sort(st+1,st+1+st_cnt);st_cnt=unique(st+1,st+st_cnt+1)-st-2;
rp(i,1,n)ad(T,i,nod[i].p);
rp(i,1,m)
rp(j,1,st_cnt)
{
rp(k,1,n)if(nod[k].r<=st[j] && st[j+1]<=nod[k].d)ad(k,name(i,j),(lf)s[i]*(st[j+1]-st[j]));
ad(name(i,j),S,s[i]*i*(st[j+1]-st[j]));
}
lf tmp=dinic();rp(i,1,n)nod[i].d-=t;
return sum-tmp<eps;
}
int main()
{
// freopen("2570.in","r",stdin);freopen("2570.out","w",stdout);
ri K=read();
while(K--)
{
ed_cnt=-1;l=0;sum=0;n=read();m=read();S=0;T=n*10+m*10;
rp(i,1,n)nod[i]=(node){read(),read(),(lf)read()},sum+=nod[i].p;rp(i,1,m)s[i]=read();ri tmp=s[1];
sort(s+1,s+1+m,cmp);s[m+1]=0;rp(i,1,m)s[i]=s[i]-s[i+1];
l=0;r=sum/tmp;while(r-l>eps){lf mid=(l+r)/2;if(check(mid))r=mid;else l=mid;}
// printf("%.6lf\n",r);
}
return 0;
}