Chlience

【题解】LUOGU 2570 [ZJOI2010]贪吃的老鼠
Problem有 $n$ 块奶酪和 $m$ 只老鼠第 $i$ 块奶酪会在 $l_i$ 时刻出现, $r_i$ 时刻...
扫描右侧二维码阅读全文
12
2019/03

【题解】LUOGU 2570 [ZJOI2010]贪吃的老鼠

Problem

有 $n$ 块奶酪和 $m$ 只老鼠

第 $i$ 块奶酪会在 $l_i$ 时刻出现, $r_i$ 时刻消失,大小为 $siz_i$
第 $i$ 只老鼠每单位时间能吃 $s_i$ 大小的奶酪

每只老鼠在每个时刻只能吃一块奶酪
每块奶酪在每个时刻只能被一只老鼠吃

假设可以将所有奶酪延长保质期 $T$ ,求能使所有奶酪被吃完的最小 $T$

Thought

说实话这道题挺不好想的...

首先,可以通过流量来表示奶酪的大小,通过将流量分配给不同的老鼠的方式视作被老鼠吃完

其次,考虑如何保证两个要求

  • 每只老鼠在每个时刻只能吃一块奶酪

    • 那么只需要保证在某个时间段内该老鼠吃掉的奶酪总量是 $s_i*t_i$ 即可
  • 每块奶酪在每个时刻只能被一只老鼠吃

    • 由于网络流的性质,很难对其直接限制;
    • 也就是说无法限制后面一个点流了流量,前面点就不流
    • 但是如果将流量进行差分,那么前面后面点同时流就表示原本的后面点直接流而前面的不流,这样就变相的完成了这个限制

具体连边方法是:

  • 对于每个奶酪从 $s$ 向其连一个流量为 $siz_i$ 的边
  • 对时间进行离散化,假设每一段时间的长度为 $t_i$
  • 对老鼠的 $s_i$ 从小到大进行排序,差分数组为 $S_i$
  • 将每个老鼠每个时刻都新建一个点,第 $k$ 只老鼠第 $j$ 时段编号为 $(j,k)$

    • 对于每个奶酪 $i$ 的每个时间段 $j$ ,分别向老鼠 $(j,k)$ 连流量为 $S[k]*t_j*(n-k+1)$ 的边,之所以要乘上 $(n-k-1)$ 是由于差分,后面点的流量也要通过这条边流出
  • 对于每个时间段 $j$ 的每只老鼠 $(j,k)$ ,向 $t$ 点连流量为 $S[k]*t_j*(n-k+1)$,这是为了限制后缀总流量,防止某只老鼠吃太多

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 35;
const double eps = 1e-5;
struct Edge {
    int t, n;
    double f;
}e[N * N * N << 2];//not sure
int head[N * N << 1], Etot = 1, cur[N * N << 1];
int f[N * N << 1], d[N * N << 1];
int s, t, cntNode, n, m, cnt;
double S[N], P[N], L[N], R[N], T[N * N << 1];
double ans;

void addedge(int u, int v, double w) {
    e[++ Etot] = {v, head[u], w};
    head[u] = Etot;
    e[++ Etot] = {u, head[v], 0};
    head[v] = Etot;
}

double dfs(int x, double flow) {
    if(x == t) return flow;
    double use = 0;
    for(int i = cur[x]; i; i = e[i].n) {
        cur[x] = i;
        if(e[i].f == 0 || d[e[i].t] + 1 != d[x]) continue;
        double tmp = dfs(e[i].t, min(flow - use, e[i].f));
        e[i].f -= tmp;
        e[i ^ 1].f += tmp;
        use += tmp;
        if(use == flow) return use;
    }
    cur[x] = head[x];
    if(!(-- f[d[x]]))
        d[s] = cntNode;
    ++ f[++ d[x]];
    return use;
}
void clear() {
    memset(f, 0, sizeof(f));
    memset(d, 0, sizeof(d));
    memset(cur, 0, sizeof(cur));
    memset(head, 0, sizeof(head));
    Etot = 1; cntNode = 0; cnt = 0; ans = 0;
    for(int i = 1; i <= n; ++ i)
        ans += P[i];
}
bool check(double mid) {
    clear();
    for(int i = 1; i <= n; ++ i) {
        T[++ cnt] = L[i];
        T[++ cnt] = mid + R[i];
    }
    sort(T + 1, T + cnt + 1);
    cnt = unique(T + 1, T + cnt + 1) - T - 1;
    cntNode = (cnt - 1) * m + n;
    s = ++ cntNode; t = ++ cntNode;
    for(int i = 1; i <= n; ++ i) {
        addedge(s, (cnt - 1) * m + i, P[i]);
        for(int j = 2; j <= cnt; ++ j) {
            if(L[i] <= T[j - 1] && mid + R[i] >= T[j]) {
                for(int k = 1; k <= m; ++ k) {
                    addedge((cnt - 1) * m + i, (j - 2) * m + k , (S[k] - S[k - 1]) * (T[j] - T[j - 1]));
                }
            }    
        }
    }
    for(int j = 2; j <= cnt; ++ j)
        for(int k = 1; k <= m; ++ k)
            addedge((j - 2) * m + k, t, (m - k + 1) * (S[k] - S[k - 1]) * (T[j] - T[j - 1]));
    f[0] = cntNode;
    while(d[s] < cntNode)
        ans -= dfs(s, 1 << 30);
    return ans <= eps;
}
void work() {
    n = read(); m = read();
    for(int i = 1; i <= n; ++ i) {
        P[i] = read();
        L[i] = read();
        R[i] = read();
    }
    for(int i = 1; i <= m; ++ i)
        S[i] = read();
    sort(S + 1, S + m + 1);
    double l = 0, r = 3000000, mid, ans = - 1;
    while(r - l >= eps) {
        mid = (l + r) / 2;
        if(check(mid))
            ans = r = mid;
        else
            l = mid;
    }
    printf("%.4f\n", ans);
}
int main() {
    int t = read();
    while(t --) work();
    return 0;
}
Last modification:March 12th, 2019 at 11:55 am

Leave a Comment