Description

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

(1) 在任一时刻,一只老鼠最多可以吃一块奶酪;

(2) 在任一时刻,一块奶酪最多被一只老鼠吃。

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

Input

输入文件的第一行包含一个整数$K$,表示输入文件中数据的组数。

每组数据的第一行包含两个整数$n$和$m$,分别表示奶酪和老鼠的数量。接下来的$n$行每行包含三个整数$p_i,r_i,d_i$。最后$m$行每行包含一个整数,表示$s_j$。$p_i,r_i,d_i,s_j$的含义如上文所述。

Output

包含K 行,每行包含一个实数,表示你找到的最小的$T$。你的答案和标准答案的绝对误差不应超过$10^{-4}$。

Solution

网络流好题!然而做法很巧(e)妙(xin)。

很容易想到二分答案(然并卵),然后用网络流判定方案是否可行,但是两个限制条件使建模难度不小。假如没有第二个限制条件,可以考虑这样一种建模:

首先考虑由源点S向所有奶酪连流量为$p[i]$的边。然后以奶酪出现和变质的时间点为界,可划分成若干个时间段,设第i个时间段的长度为$dur[i]$,将每个老鼠按时间段拆成若干个点,向汇点T连流量为 $s[j] * dur[i]$。最后奶酪向其对应时间段内的老鼠连边 $s[j] * dur[i]$。

这样的连边显然无法保证某个奶酪在任意时间点不会被多个老鼠吃。我们考虑先将老鼠按s从大到小排序,再令$s[i] = s[i] - s[i+1]$,而奶酪向老鼠的连边流量仍为 $s[i] * dur[i]$。这样我们考虑某一个时间段,若该奶酪向老鼠j连边的流量与s[j]之比为t[j],令t[j]随j递增(主要是为了理解方便),该奶酪出流量:

我们发现,此时该奶酪被老鼠吃的总时间就是 $t[m]$,由于流量限制我们可以保证$t[m] < dur[i]$,且第$j(j > 1)$只老鼠吃奶酪的实际时间是$t[j] - t[j-1]$,因而可以考虑到所有情况。此时老鼠向汇的连边流量也需要调整,第$j$只老鼠的第$i$个时间段与汇的流量上限为$s[j] * dur[i] * j$,这是因为当某只老鼠被选择时,所有编号在它后面的老鼠的节点也需要增加相应的流量。

Source

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>

#define For(i,j,k) for(int i = j;i <= ((int)k);i++)
#define Forr(i,j,k) for(int i = j;i >= (k);i--)
#define Set(i,j) memset(i, j, sizeof(i))
#define pb push_back

using namespace std;

const double eps = 1e-9;
const int N = 2010, M = 200010;

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

struct Edge{
	int to;
	double cap, flow;
};

struct Dinic{
	Edge E[M];
	vector<int> G[N];
	int n, e, S, T;
	int dis[N], cur[N], vis[N];

	void init(int _n){
		n = _n;
		For(i,0,n) G[i].clear();
		e = -1;	
	}

	void Add(int x, int y, double w){
		G[x].pb(++e), E[e] = (Edge){y, w, 0};
		G[y].pb(++e), E[e] = (Edge){x, 0, 0};
	}

	bool BFS(){
		queue<int> q;
		Set(vis, false);
		q.push(S), vis[S] = true;
		while(!q.empty()){
			int h = q.front(); q.pop();
			For(i,0,G[h].size() - 1){
				Edge d = E[G[h][i]];
				if(vis[d.to] || dcmp(d.cap - d.flow) <= 0) continue;
				dis[d.to] = dis[h] + 1, vis[d.to] = true;
				q.push(d.to);
			}
		}
		return vis[T];
	}

	double DFS(int h, double f){
		if(h == T) return f;
		double t = 0, sumf = 0;
		for(int &i = cur[h];i < (int)G[h].size();++i){
			Edge &d = E[G[h][i]];
			if(dcmp(f) <= 0) break;
			if(dis[d.to] == dis[h] + 1 
			&& dcmp(t = DFS(d.to, min(f, d.cap - d.flow))) > 0){
				f -= t;
				sumf += t;
				d.flow += t;
				E[G[h][i] ^ 1].flow -= t;
			}
		}
		return sumf;
	}

	double Maxflow(int s, int t){
		S = s, T = t;
		double ret = 0;
		while(BFS()){
			Set(cur, 0);
			ret += DFS(S, 1e9);
		}
		return ret;
	}

}F;

int p[N], l[N], r[N], s[N];
int TEST, n, m;

double Time[N], sump;

bool check(double v){
	For(i,1,n) Time[i] = l[i], Time[i + n] = r[i] + v;
	sort(Time + 1, Time + 2 * n + 1);
	int S = 0, T = n + 2 * n * m + 1;
	F.init(T);
	For(i,1,n) F.Add(S, i, p[i]);
	For(i,2,n / 2){
		double dur = Time[i] - Time[i-1];
		if(!dcmp(dur)) continue;
		For(j,1,m){
			double h = n + m * (i - 1) + j;
			F.Add(h, T, j * s[j] * dur);
			For(k,1,n)
				if(dcmp(Time[i-1] - l[k]) >= 0 && 
				   dcmp(Time[i] - r[k] - v) <= 0) 
					F.Add(k, h, s[j] * dur);
		}
	}
	return dcmp(F.Maxflow(S, T) - sump) >= 0;
}

int main(){
	scanf("%d", &TEST);
	while(TEST--){
		scanf("%d%d", &n, &m);
		sump = 0;
		For(i,1,n) 
		    scanf("%d%d%d", &p[i], &l[i], &r[i]), sump += p[i];
		For(i,1,m) scanf("%d", &s[i]);
		sort(s + 1, s + m + 1, greater<int>());
		For(i,1,m-1) s[i] -= s[i+1];
		double L = 0, R = 3e6;
		while(R - L > eps){
			double Mid = (L + R) / 2;
			if(check(Mid)) R = Mid;
			else L = Mid;
		}
		printf("%.6lf\n", L);
	}
	return 0;
}