Luogu2570 [ZJOI2010]贪吃的老鼠
题面描述
https://www.luogu.org/problemnew/show/P2570
然后题意大概就是m只老鼠，然后吃n个奶酪，已知
- 每个奶酪体积为$p_i$
- 每个奶酪原始保质期为$s_i到t_i$（在一个时间轴上的位置）
- 每只老鼠吃奶酪的速度为$v_i$
要求
- 同一时刻老鼠不能被原谅（不能吃两块奶酪）
- 同一时刻奶酪不能原谅（不能被两只老鼠吃）
老鼠吃奶酪的时间可以为小数，且一个老鼠“一生”可以吃多块奶酪，一块奶酪“一生”可以多次被吃
现在你可以为奶酪$+T\ s$，也就是对于所有奶酪$t_i += T$
现在让你最小化$T$
题解
<!--瞎BB开始-->
好像机房就我没写了......
反正是要看题解的，这辈子逃不开题解的......
但题解看不懂连生活都维持不了这样子......
<!--瞎BB结束-->
还是DL不能依靠，还是自己看比较好
二分答案+最大流
建图方式：
首先对所有时间点离散化，记两个时间点之间的时间段长度为$tim$，然后把老鼠从大到小排序最后加个数字0，差分得到m个差分值，记为d，依次编号为$1,2,3...$
对奶酪建点，对时间点间的时间段拆点，拆成m个老鼠差分值
源点连向奶酪，容量 p
奶酪连向奶酪保质期内的时间段的老鼠差分点，容量为 老鼠差分值*时间段长度
老鼠差分点连向终点，容量为 老鼠差分值*时间段长度*老鼠差分点编号（排序后从大到小）
然后跑最大流，奶酪满流即为合法
下面配合一个实例来讲解证明为什么这样是对的（反正我是想不到的）
为了区分老鼠速度和差分后的速度，我们将拆出来的点称为“老鼠差分点“或”老鼠点“或指代意义的”点“
举个例子
老鼠分别有速度7,4,2
差分得到3,2,2
然后我们假设时间段长度为2
然后老鼠到t的流量限制为6,8,12
然后和奶酪的流量限制为6,4,4
当且仅当这张图所有奶酪到起点的边满流的时候有解，其中如果一个老鼠$x$在一个时间段内吃了奶酪$y$，那么从该时间段$m-x$到$m$的老鼠差分点到奶酪$y$都会有流量$t*d_i$。这张图的工作原理是比较简单的（如果看不懂可以参考一下其它DL的博客）
最主要难以证明的是题目需要满足的两个要求。
首先证明这张图满足一个老鼠同一时间只吃一个奶酪
如果一个从大到小排名第$k$的老鼠吃了同一时间段的$x$块奶酪（如果不在同一时间段的话就不会有非法状态，如果有重叠则重叠部分和这个问题等价），设第$i$块奶酪吃了时间$t_i$，那么我们假设一个非法状态，也就是$(\Sigma{t_i}) > tim$，也就是一个老鼠同时吃多块奶酪，所以这个时候k号老鼠差分点产生的流量至少为$\Sigma{(t_i)}*d_k$，我们记为流量，但是我们对该老鼠的限制有$k*tim*d_k$，我们记为容量，我们要证明非法状态的$流量 > 容量$，在网络流中不存在。
这个时候我们有两种情况：
- 速度更快的老鼠还可以吃且可以吃超额部分（超额部分就是引起一只老鼠需要在同一时间吃两个奶酪的部分），那么就可以分担这个老鼠的任务，所以不存在这样的非法状态
- 速度更快的老鼠吃不完超额部分，那么这些老鼠一定是已经吃过了，所以根据差分上面$k-1$个老鼠差分点对这个老鼠差分点产生了流量负担，这个负担加上原有的流量为$\Sigma{(t_i)}*d_k+(k-1)*d_k*tim=k*tim*t_k+(\Sigma{(t_i)}-tim)$，由于$(\Sigma{(t_i)}-tim)>0$，所以$\Sigma{(t_i)}*d_k+(k-1)*d_k*tim>k*d_k*tim$，所以$流量 > 容量$，在网络流中无法实现
然后证明这张图满足一个奶酪同时只被一只老鼠吃
这个比较简单，一样假设一共有x只老鼠吃了奶酪，每一个吃了时间$t_i$，然后假设非法状态$(\Sigma{t_i}) > tim$，然后由于排名靠前的老鼠吃了的话那么在差分点中对排名较后的老鼠也会有时间上的影响，也就是吃了同一个奶酪的排名最后的老鼠流量为$\Sigma{(t_i)}*d_k$，大于边的容量$ti*d_k$，所以状态不存在。
代码如下：
1 #include <cstdio> 2 #include <cctype> 3 #include <cstring> 4 #include <iostream> 5 6 //User's Lib 7 8 #include <cmath> 9 #include <algorithm> 10 11 using namespace std; 12 13 #define DEBUG_PORT 14 #define DEBUG 15 16 #ifdef ONLINE_JUDGE 17 #undef DEBUG_PORT 18 #undef DEBUG 19 #endif 20 21 #ifdef DEBUG_PORT 22 #if __cplusplus >= 201103L 23 #ifdef DEBUG 24 template<typename T> 25 extern inline void Debug(T tar){ 26 cerr << tar << endl; 27 } 28 template<typename Head, typename T, typename... Tail> 29 extern inline void Debug(Head head, T mid, Tail... tail){ 30 cerr << head << ' '; 31 Debug(mid, tail...); 32 } 33 #else 34 # pragma GCC diagnostic push 35 # pragma GCC diagnostic ignored "-Wunused-parameter" 36 template<typename Head, typename T, typename... Tail> 37 extern inline void Debug(Head head, T mid, Tail... tail){ 38 return ; 39 } 40 # pragma GCC diagnostic pop 41 # pragma message "Warning : pragma used" 42 #endif 43 #else 44 # pragma message "Warning : C++11 Not Use" 45 #ifdef DEBUG 46 template <typename T> 47 extern inline void Debug(T tar){ 48 cerr << tar << endl; 49 } 50 #else 51 # pragma GCC diagnostic push 52 # pragma GCC diagnostic ignored "-Wunused-parameter" 53 template <typename T> 54 extern inline void Debug(T tar){ 55 return ; 56 } 57 # pragma GCC diagnostic pop 58 # pragma message "Warning : pragma used" 59 #endif 60 #endif 61 #else 62 # pragma GCC diagnostic push 63 # pragma GCC diagnostic ignored "-Wunused-parameter" 64 template<typename Head, typename T, typename... Tail> 65 extern inline void Debug(Head head, T mid, Tail... tail){ 66 return ; 67 } 68 template <typename T> 69 extern inline void Debug(T tar){ 70 return ; 71 } 72 # pragma GCC diagnostic pop 73 # pragma message "Warning : pragma used" 74 #endif 75 76 char buf[11111111], *pc = buf; 77 78 extern inline void Main_Init(){ 79 static bool INITED = false; 80 if(INITED) fclose(stdin), fclose(stdout); 81 else { 82 fread(buf, 1, 11111111, stdin); 83 INITED = true; 84 } 85 } 86 87 static inline int read(){ 88 int num = 0; 89 char c, sf = 1; 90 while(isspace(c = *pc++)); 91 if(c == 45) sf = -1, c = *pc ++; 92 while(num = num * 10 + c - 48, isdigit(c = *pc++)); 93 return num * sf; 94 } 95 96 namespace LKF{ 97 template <typename T> 98 extern inline T abs(T tar){ 99 return tar < 0 ? -tar : tar; 100 } 101 template <typename T> 102 extern inline void swap(T &a, T &b){ 103 T t = a; 104 a = b; 105 b = t; 106 } 107 template <typename T> 108 extern inline void upmax(T &x, const T &y){ 109 if(x < y) x = y; 110 } 111 template <typename T> 112 extern inline void upmin(T &x, const T &y){ 113 if(x > y) x = y; 114 } 115 template <typename T> 116 extern inline T max(T a, T b){ 117 return a > b ? a : b; 118 } 119 template <typename T> 120 extern inline T min(T a, T b){ 121 return a < b ? a : b; 122 } 123 } 124 125 //Source Code 126 127 const int MAXK = 33; 128 const int MAXN = 2018; 129 const int MAXM = 99999; 130 const double INF = 1e16; 131 const double eps = 1e-6; 132 133 inline bool comp(const double &a, const double &b){ 134 double tmp = a - b;//int??? 135 if(fabs(tmp) < eps) return 0; 136 return a > b ? 1 : -1; 137 } 138 139 int s = MAXN - 10, t = s + 1; 140 141 struct Queue{ 142 int s, t; 143 int q[MAXN]; 144 Queue(){s = 1, t = 0;} 145 inline void clear(){ 146 s = 1, t = 0; 147 } 148 inline bool empty(){ 149 return s > t; 150 } 151 inline int size(){ 152 return t - s + 1; 153 } 154 inline void push(int tar){ 155 q[++ t] = tar; 156 } 157 inline int front(){ 158 return q[s]; 159 } 160 inline void pop(){ 161 s ++; 162 } 163 }; 164 165 struct Graph{ 166 int tot; 167 int beginx[MAXN], endx[MAXM], nxt[MAXM]; 168 double res[MAXM]; 169 Graph(){ 170 tot = 1; 171 } 172 inline void Init(){ 173 tot = 1; 174 memset(beginx, 0, sizeof(beginx)); 175 } 176 inline void add_edge(int u, int v, double r){ 177 // Debug(u, "->", v, "[label = \"", r, "\"]");//Debug... 178 nxt[++ tot] = beginx[u], beginx[u] = tot, endx[tot] = v, res[tot] = r; 179 nxt[++ tot] = beginx[v], beginx[v] = tot, endx[tot] = u, res[tot] = 0; 180 } 181 }; 182 183 struct ISap{ 184 Graph g; 185 Queue mession; 186 double max_f; 187 int cur[MAXN], d[MAXN], num[MAXN], pre[MAXN]; 188 inline void bfs(){ 189 mession.clear(); 190 mession.push(t); 191 memset(d, 0, sizeof(d)); 192 memset(num, 0, sizeof(num)); 193 d[t] = 1; 194 int u, v; 195 while(!mession.empty()){ 196 u = mession.front(); 197 mession.pop(); 198 num[d[u]] ++; 199 for(int i = g.beginx[u]; i; i = g.nxt[i]){ 200 v = g.endx[i]; 201 if(!d[v] && comp(g.res[i ^ 1], 0)){ 202 d[v] = d[u] + 1; 203 mession.push(v); 204 } 205 } 206 } 207 } 208 inline double dfs(int u, double now_f){ 209 if(u == t) return now_f; 210 double ret_f = 0; 211 for(int &i = cur[u]; i; i = g.nxt[i]){ 212 int v = g.endx[i]; 213 if(comp(g.res[i], 0) && d[u] == d[v] + 1){ 214 double ret = dfs(v, min(g.res[i], now_f)); 215 ret_f += ret, now_f -= ret; 216 g.res[i] -= ret, g.res[i ^ 1] += ret; 217 if(d[s] >= MAXN - 4 || !comp(now_f, 0)) return ret_f; 218 } 219 } 220 if(-- num[d[u]] == 0) d[s] = MAXN - 4; 221 ++ num[++ d[u]]; 222 cur[u] = g.beginx[u]; 223 return ret_f; 224 } 225 inline double ISAP(){ 226 bfs(); 227 max_f = 0; 228 memcpy(cur, g.beginx, sizeof(cur)); 229 while(d[s] < MAXN - 5) 230 max_f += dfs(s, INF); 231 return max_f; 232 } 233 }isap; 234 235 int n, m, sum; 236 int p[MAXK], r[MAXK], d[MAXK], ss[MAXK]; 237 double tmp_arr[MAXK << 1]; 238 int cnt; 239 240 inline bool check(double tar){ 241 cnt = 0; 242 isap.g.Init(); 243 for(int i = 1; i <= n; i++) 244 tmp_arr[++ cnt] = r[i], tmp_arr[++ cnt] = d[i] + tar; 245 sort(tmp_arr + 1, tmp_arr + 1 + cnt); 246 cnt = unique(tmp_arr + 1, tmp_arr + 1 + cnt) - tmp_arr - 1; 247 for(int i = 1; i <= n; i++) 248 isap.g.add_edge(s, i, p[i]); 249 for(int i = 2; i <= cnt; i++){ 250 double lst = tmp_arr[i - 1], tim = tmp_arr[i] - lst; 251 for(int j = 1; j <= m; j++) 252 isap.g.add_edge(n + (i - 2) * m + j, t, j * tim * ss[j]); 253 for(int j = 1; j <= n; j++) 254 if(r[j] <= lst && d[j] + tar >= tmp_arr[i]) 255 for(int k = 1; k <= m; k++) 256 isap.g.add_edge(j, n + (i - 2) * m + k, tim * ss[k]); 257 } 258 return !comp(isap.ISAP(), sum); 259 } 260 261 int main(){ 262 Main_Init(); 263 int T = read(); 264 while(T --){ 265 n = read(), m = read(); 266 sum = 0; 267 for(int i = 1; i <= n; i++) 268 sum += (p[i] = read()), r[i] = read(), d[i] = read(); 269 for(int i = 1; i <= m; i++) 270 ss[i] = read(); 271 ss[m + 1] = 0; 272 int tmp = ss[1]; 273 sort(ss + 1, ss + 1 + m, greater<int>()); 274 for(int i = 1; i <= m; i++) 275 ss[i] -= ss[i + 1]; 276 double l = 0, r = 1.0 * sum / tmp, mid; 277 while(fabs(r - l) > eps){ 278 mid = (l + r) / 2.0; 279 if(check(mid)) r = mid; 280 else l = mid; 281 } 282 printf("%.5lf\n", mid); 283 } 284 Main_Init(); 285 return 0; 286 }