「ZJOI2010」贪吃的老鼠 - 二分+拆点+网络流

题目大意

    奶酪店里最近出现了$m$只老鼠！它们的目标就是把生产出来的所有奶酪都吃掉。奶酪店中一天会生产$n$块奶酪，其中第$i$块的大小为$p_i$，会在第$r_i$秒被生产出来，并且必须在第$d_i$秒之前将它吃掉。第$j$只老鼠吃奶酪的速度为$s_j$，因此如果它单独吃完第$i$快奶酪所需的时间为$p_i$/$s_j$。老鼠们吃奶酪的习惯很独特，具体来说：

1. 在任一时刻，一只老鼠最多可以吃一块奶酪；

2. 在任一时刻，一块奶酪最多被一只老鼠吃。

    由于奶酪的保质期常常很短，为了将它们全部吃掉，老鼠们需要使用一种神奇的魔法来延长奶酪的保质期。将奶酪的保质期延长$T$秒是指所有的奶酪的$d_i$变成$d_i+T$。同时，使用魔法的代价很高，因此老鼠们希望找到最小的$T$使得可以吃掉所有的奶酪。

---

题目分析

本题的建图方式非常玄学，然而看本题时我根本没想到是网络流，当成DP想了半天（完了我现在看DP是网络流，看网络流是DP）。

首先二分答案和将时间离散化是很容易想到的。

现在先不考虑在一个时刻，每一块奶酪只能被一只老鼠吃。
那么我们可以得到这样的建图方法：

• 源点向奶酪连边，容量为奶酪大小。
• 将老鼠按照离散化后的时间段拆点，每一个时间段向对应的可以吃的奶酪连边，容量为老鼠的速度$v\times dur$，其中$dur$是时间段大小。
• 老鼠向汇点连边，容量INF。

现在我们来考虑每一块奶酪只能被一只老鼠吃。
将老鼠按速度排序后做个差分。
如9 4 1改为5 3 1。
修改建图方式：

• 源点向奶酪连边，容量为奶酪大小。
• 将老鼠按照离散化后的时间段拆点，每一个时间段向对应的可以吃的奶酪连边，容量为老鼠的差分后速度$v\times dur$，其中$dur$是时间段大小。
• 编号为$i$的老鼠向汇点连边，容量为差分后速度$i\times v[i]\times dur$。

我们来解释一下这样建图的原因。
先考虑每一块奶酪只能被一只老鼠吃。
首先，可以吃的奶酪量可以看做各个老鼠速度的线性组合。
而差分后线性基没有改变，所以张量不变。
其次，由于时间可以无限拆分，那么张量最大值即为老鼠差分后速度之和，即为吃的最快的老鼠原速度，因此张量$=0\sim$ 最大值。因此我们只需要限制最大值即可，在第二种建边的时候已经限制，全部满流时最大。
然后，考虑每一只老鼠只能吃一块奶酪。
类似上面所说的，我们可以将老鼠吃不同的奶酪也看做线性组合，同样只需要限制最大值，即为所有老鼠一起吃奶酪，在第三种建边时已经限制，全部满流时最大。

---

代码

#include<bits/stdc++.h>

using namespace std;

inline int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
	while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
	return num*bj;
}

const int maxn=3005;
const double eps=1e-6;

int dcmp(double x) {
	if(fabs(x)<=eps)return 0;
	return x>eps?1:-1;
}

struct Edge {
	int from,to;
	double cap,flow;
	Edge(int x=0,int y=0,double c=0,double f=0):from(x),to(y),cap(c),flow(f) {}
};

struct Dinic {
	int n,m,s,t;
	vector<Edge> edges;
	vector<int> G[maxn];
	bool vst[maxn];
	int dist[maxn],cur[maxn];
	void init(int n) {
		this->n=n;
		edges.clear();
		for(int i=1; i<=n; i++)G[i].clear();
	}
	void AddEdge(int x,int y,double v) {
		edges.push_back(Edge(x,y,v,0));
		edges.push_back(Edge(y,x,0,0));
		m=edges.size();
		G[x].push_back(m-2);
		G[y].push_back(m-1);
	}
	bool bfs() {
		fill(vst+1,vst+n+1,0);
		queue<int> Q;
		Q.push(t);
		vst[t]=1;
		while(!Q.empty()) {
			int Now=Q.front();
			Q.pop();
			for(int id:G[Now]) {
				Edge& e=edges[id^1];
				int Next=e.from;
				if(!vst[Next]&&dcmp(e.cap-e.flow)>0) { 
					vst[Next]=1;
					dist[Next]=dist[Now]+1;
					if(Next==s)return 1;
					Q.push(Next);
				}
			}
		}
		return vst[s];
	}
	double dfs(int Now,double a) {
		if(Now==t||dcmp(a)==0)return a;
		double flow=0;
		for(int &i=cur[Now]; i<G[Now].size(); i++) {
			int id=G[Now][i];
			Edge &e=edges[id];
			int Next=e.to;
			if(dist[Now]-1!=dist[Next])continue;
			double nextflow=dfs(Next,min(a,e.cap-e.flow));
			if(dcmp(nextflow)>0) {
				e.flow+=nextflow;
				edges[id^1].flow-=nextflow;
				flow+=nextflow;
				a-=nextflow;
				if(a==0)break;
			}
		}
		return flow;
	}
	double maxflow(int s,int t) {
		this->s=s;
		this->t=t;
		double flow=0;
		while(bfs()) {
			memset(cur,0,sizeof(cur));
			flow+=dfs(s,1e18);
		}
		return flow;
	}
} dinic;

struct Cheese {
	int p,x,y;
} a[maxn];

int n,m,v[maxn],sum=0;
double Time[maxn];

bool Check(double t) {
	int S=n+n*m*2+1,T=n+n*m*2+2;
	dinic.init(T);
	for(int i=1; i<=n; i++) {
		dinic.AddEdge(S,i,a[i].p);
		Time[i]=a[i].x;
		Time[n+i]=a[i].y+t;
	}
	sort(Time+1,Time+2*n+1);
	for(int i=2; i<=2*n; i++) {
		double x=Time[i]-Time[i-1];
		if(x<eps)continue;
		for(int j=1; j<=m; j++) {
			int y=n+(i-1)*m+j;
			dinic.AddEdge(y,T,j*v[j]*x);
			for(int k=1; k<=n; k++)
				if(dcmp(Time[i-1]-a[k].x)>=0&&dcmp(Time[i]-a[k].y-t)<=0)dinic.AddEdge(k,y,v[j]*x);
		}
	}
	return dcmp(dinic.maxflow(S,T)-sum)>=0;
}

int main() {
	int t=Get_Int();
	while(t--) {
		n=Get_Int();
		m=Get_Int();
		sum=0;
		for(int i=1; i<=n; i++) {
			a[i].p=Get_Int();
			a[i].x=Get_Int();
			a[i].y=Get_Int();
			sum+=a[i].p;
		}
		for(int i=1; i<=m; i++)v[i]=Get_Int();
		double Left=0,Right=sum/v[1]+1;
		sort(v+1,v+m+1,greater<int>());
		for(int i=1; i<m; i++)v[i]-=v[i+1];
		while(Right-Left>eps) {
			double mid=(Left+Right)/2;
			if(Check(mid))Right=mid;
			else Left=mid;
		}
		printf("%0.4lf\n",(Left+Right)/2);
	}
	return 0;
}