题目描述
奶酪店里最近出现了m只老鼠！它们的目标就是把生产出来的所有奶酪都吃掉。奶酪店中一天会生产n块奶酪，其中第i块的大小为pi，会在第ri秒被生产出来，并且必须在第di秒之前将它吃掉。第j只老鼠吃奶酪的速度为sj，因此如果它单独吃完第i快奶酪所需的时间为pi/sj。老鼠们吃奶酪的习惯很独特，具体来说： (1) 在任一时刻，一只老鼠最多可以吃一块奶酪； (2) 在任一时刻，一块奶酪最多被一只老鼠吃。 由于奶酪的保质期常常很短，为了将它们全部吃掉，老鼠们需要使用一种神奇的魔法来延长奶酪的保质期。将奶酪的保质期延长T秒是指所有的奶酪的di变成di+T。同时，使用魔法的代价很高，因此老鼠们希望找到最小的T使得可以吃掉所有的奶酪。
输入输出格式 输入格式：
输入文件的第一行包含一个整数K，表示输入文件中数据的组数。 每组数据的第一行包含两个整数n和m，分别表示奶酪和老鼠的数量。接下来的n行每行包含三个整数pi,ri,di。最后m行每行包含一个整数，表示sj。pi,ri,di,sj的含义如上文所述。
输出格式：
包含K 行，每行包含一个实数，表示你找到的最小的T。你的答案和标准答案的绝对误差不应超过10−4。
输入输出样例 输入样例#1：
2 2 2 13 0 4 10 1 3 4 2 1 1 1 0 2 1 输出样例#1： 0.5 0
这网络流真恶心
看了半天题解然而还是没懂
胡诌一下
就是我们先二分需要延长多长的时间
然后进行判断
看在延长这么长的时间后是否能吃完所有的奶酪
并从源点向每个奶酪连流量为p[i]的边
现在考虑题目的两个限制条件 ：
(1) 在任一时刻，一只老鼠最多可以吃一块奶酪；
(2) 在任一时刻，一块奶酪最多被一只老鼠吃。
所以我们将所有的老鼠吃奶酪的速度从小到大排序
然后进行差分
再从老鼠向汇点连流量为 i * v[i] * 时间段长短
举个栗子
9 = 3+4+1+1 6 = 4+1+1 2 = 1+1 1 = 1 9+6+2+1 = 31 + 42 + 13 + 14
我们可以发现，所有的老鼠经过差分后的速度总和最多就和所有老鼠都在吃奶酪一样了
这样我们可以按照时间拆点
拆出每个奶酪的出现点和变质点
然后将合法时间（出现且没有变质）的奶酪向相应时间段的老鼠连流量为v[i] * 时间段的边
这样就可以保证每个奶酪最快的被吃速度为吃的最快的老鼠吃的速度
跑最大流看是否能吃完所有的奶酪就好辣
这题真恶心
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
const int M = 105 ;
const int N = 5005 ;
const double eps = 1e-7 ;
const double inf = 210000000000000000LL ;
inline double read(){
double x=0,w=1;char c=getchar();
while(c>'9'||c<'0'){if(c=='-') w=-1 ;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar(); }
return x*w;
}
struct Cake{
double p,r,d;
}c[M];
struct E{
int nex,to;
double dis;
}edge[N<<5];
int n,m;
double v[M],tot,tim[M];
int hea[N],num=1;
int s,t;
int d[N];
inline void ins(int from,int to,double dis){
edge[++num].nex=hea[from];
edge[num].to=to;
edge[num].dis=dis;
hea[from]=num;
}
inline void add_edge(int from,int to,double dis){
ins(from,to,dis);
ins(to,from,0);
}
inline bool cmp(int a,int b){return a>b;}
inline bool bfs(){
queue<int>q; q.push(s);
memset(d,0,sizeof(d)); d[s]=1;
while(!q.empty()){
int u=q.front(); q.pop();
for(int i=hea[u];i;i=edge[i].nex){
int v=edge[i].to;
if(!d[v]&&edge[i].dis>=eps){
d[v]=d[u]+1;
q.push(v);
}
}
}
return d[t];
}
double Dfs(int u,double dis){
if(u==t||dis<eps) return dis;
double sum=0;
for(int i=hea[u];i;i=edge[i].nex){
int v=edge[i].to;
if(d[v]==d[u]+1&&edge[i].dis){
double diss=Dfs(v,min(dis,edge[i].dis));
if(diss>eps){
edge[i].dis-=diss;
edge[i^1].dis+=diss;
dis-=diss;
sum+=diss;
if(dis<=eps) break;
}
}
}
if(sum<=eps) d[u]=-1;
return sum;
}
inline double dinic(){
double temp=0;
while(bfs())
temp+=Dfs(s,inf);
return temp;
}
inline int check(double k){
if(fabs(k)<eps) return 0;
return k>0 ? 1 : -1 ;
}
inline bool judge(double mid){
memset(edge,0,sizeof(edge));
memset(hea,0,sizeof(hea));
num=1;
s=0; t=n+n*m*2+3;
for(int i=1;i<=n;i++){
add_edge(s,i,c[i].p);
tim[i]=c[i].r;
tim[i+n]=c[i].d+mid;
}
sort(tim+1,tim+n*2+1);
for(int i=2;i<=n*2;i++){
double x=tim[i]-tim[i-1];
if(x<eps) continue ;
for(int j=1;j<=m;j++){
int y=n+(i-1)*m+j;
add_edge(y,t,j*v[j]*x);
for(int k=1;k<=n;k++)
if(check(tim[i-1]-c[k].r)>=0&&check(tim[i]-c[k].d-mid)<=0)
add_edge(k,y,v[j]*x);
}
}
double temp=dinic();
return temp-tot>=0;
}
double Ans;
int main(){
int T;
scanf("%d",&T);
while(T--){
memset(v,0,sizeof(v));
tot=0;
Ans=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
c[i].p=read();
c[i].r=read();
c[i].d=read();
tot+=c[i].p;
}
for(int i=1;i<=m;i++) v[i]=read();
sort(v+1,v+m+1,cmp);
double L=0,R=tot/v[1]+2;
for(int i=1;i<=m;i++)
v[i]-=v[i+1];
while(R-L>eps){
double mid=(L+R)/2.0;
if(judge(mid)) R=mid,Ans=mid;
else L=mid;
}
printf("%lf\n",Ans);
}
return 0;
}