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

Creeper_LKF · 2018-06-13 00:39:49 · 题解

宣传

首先宣传一波：我的博客

题面

原题面还是比较简洁的，不描述了

题解

这份题解主要在于证明，解法也会提到，如果有疑问可以参考其它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，我们记为容量，我们要证明非法状态的流量 > 容量，在网络流中不存在。
这个时候我们有两种情况：
1. --------速度更快的老鼠还可以吃且可以吃超额部分（超额部分就是引起一只老鼠需要在同一时间吃两个奶酪的部分），那么就可以分担这个老鼠的任务，所以不存在这样的非法状态
2. ---------速度更快的老鼠吃不完超额部分，那么这些老鼠一定是已经吃过了，所以根据差分上面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，所以状态不存在。

代码如下：

#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>

//User's Lib

#include <cmath>
#include <algorithm>

using namespace std;

#define DEBUG_PORT
#define DEBUG

#ifdef ONLINE_JUDGE
#undef DEBUG_PORT
#undef DEBUG
#endif

#ifdef DEBUG_PORT
#if __cplusplus >= 201103L
#ifdef DEBUG
template<typename T>
extern inline void Debug(T tar){
    cerr << tar << endl;
}
template<typename Head, typename T, typename... Tail>
extern inline void Debug(Head head, T mid, Tail... tail){
    cerr << head << ' ';
    Debug(mid, tail...);
}
#else
# pragma GCC diagnostic push
# pragma GCC diagnostic ignored "-Wunused-parameter"
template<typename Head, typename T, typename... Tail>
extern inline void Debug(Head head, T mid, Tail... tail){
    return ;
}
# pragma GCC diagnostic pop
# pragma message "Warning : pragma used"
#endif
#else
# pragma message "Warning : C++11 Not Use"
#ifdef DEBUG
template <typename T>
extern inline void Debug(T tar){
    cerr << tar << endl;
}
#else
# pragma GCC diagnostic push
# pragma GCC diagnostic ignored "-Wunused-parameter"
template <typename T>
extern inline void Debug(T tar){
    return ;
}
# pragma GCC diagnostic pop
# pragma message "Warning : pragma used"
#endif
#endif
#else
# pragma GCC diagnostic push
# pragma GCC diagnostic ignored "-Wunused-parameter"
template<typename Head, typename T, typename... Tail>
extern inline void Debug(Head head, T mid, Tail... tail){
    return ;
}
template <typename T>
extern inline void Debug(T tar){
    return ;
}
# pragma GCC diagnostic pop
# pragma message "Warning : pragma used"
#endif

char buf[11111111], *pc = buf;

extern inline void Main_Init(){
    static bool INITED = false;
    if(INITED) fclose(stdin), fclose(stdout);
    else {
        fread(buf, 1, 11111111, stdin); 
        INITED = true;           
    }
}

static inline int read(){
    int num = 0;
    char c, sf = 1;
    while(isspace(c = *pc++));
    if(c == 45) sf = -1, c = *pc ++;
    while(num = num * 10 + c - 48, isdigit(c = *pc++));
    return num * sf;
}

namespace LKF{
    template <typename T>
    extern inline T abs(T tar){
        return tar < 0 ? -tar : tar;
    }
    template <typename T>
    extern inline void swap(T &a, T &b){
        T t = a;
        a = b;
        b = t;
    }
    template <typename T>
    extern inline void upmax(T &x, const T &y){
        if(x < y) x = y;
    }
    template <typename T>
    extern inline void upmin(T &x, const T &y){
        if(x > y) x = y;
    }
    template <typename T>
    extern inline T max(T a, T b){
        return a > b ? a : b;
    }
    template <typename T>
    extern inline T min(T a, T b){
        return a < b ? a : b;
    }
}

//Source Code

const int MAXK = 33;
const int MAXN = 2018;
const int MAXM = 99999;
const double INF = 1e16;
const double eps = 1e-6;

inline bool comp(const double &a, const double &b){
    double tmp = a - b;//int???
    if(fabs(tmp) < eps) return 0;
    return a > b ? 1 : -1;
}

int s = MAXN - 10, t = s + 1;

struct Queue{
    int s, t;
    int q[MAXN];
    Queue(){s = 1, t = 0;}
    inline void clear(){
        s = 1, t = 0;
    }
    inline bool empty(){
        return s > t;
    }
    inline int size(){
        return t - s + 1;
    }
    inline void push(int tar){
        q[++ t] = tar;
    }
    inline int front(){
        return q[s];
    }
    inline void pop(){
        s ++;
    }
};

struct Graph{
    int tot;
    int beginx[MAXN], endx[MAXM], nxt[MAXM];
    double res[MAXM];
    Graph(){
        tot = 1;
    }
    inline void Init(){
        tot = 1;
        memset(beginx, 0, sizeof(beginx));
    }
    inline void add_edge(int u, int v, double r){
        // Debug(u, "->", v, "[label = \"", r, "\"]");//Debug...
        nxt[++ tot] = beginx[u], beginx[u] = tot, endx[tot] = v, res[tot] = r;
        nxt[++ tot] = beginx[v], beginx[v] = tot, endx[tot] = u, res[tot] = 0;
    }
};

struct ISap{
    Graph g;
    Queue mession;
    double max_f;
    int cur[MAXN], d[MAXN], num[MAXN], pre[MAXN];
    inline void bfs(){
        mession.clear();
        mession.push(t);
        memset(d, 0, sizeof(d));
        memset(num, 0, sizeof(num));
        d[t] = 1;
        int u, v;
        while(!mession.empty()){
            u = mession.front();
            mession.pop();
            num[d[u]] ++;
            for(int i = g.beginx[u]; i; i = g.nxt[i]){
                v = g.endx[i];
                if(!d[v] && comp(g.res[i ^ 1], 0)){
                    d[v] = d[u] + 1;
                    mession.push(v);
                }
            }
        }
    }
    inline double dfs(int u, double now_f){
        if(u == t) return now_f;
        double ret_f = 0;
        for(int &i = cur[u]; i; i = g.nxt[i]){
            int v = g.endx[i];
            if(comp(g.res[i], 0) && d[u] == d[v] + 1){
                double ret = dfs(v, min(g.res[i], now_f));
                ret_f += ret, now_f -= ret;
                g.res[i] -= ret, g.res[i ^ 1] += ret;
                if(d[s] >= MAXN - 4 || !comp(now_f, 0)) return ret_f;
            }
        }
        if(-- num[d[u]] == 0) d[s] = MAXN - 4;
        ++ num[++ d[u]];
        cur[u] = g.beginx[u];
        return ret_f;
    }
    inline double ISAP(){
        bfs();
        max_f = 0;
        memcpy(cur, g.beginx, sizeof(cur));
        while(d[s] < MAXN - 5)
            max_f += dfs(s, INF);
        return max_f;
    }
}isap;

int n, m, sum;
int p[MAXK], r[MAXK], d[MAXK], ss[MAXK];
double tmp_arr[MAXK << 1];
int cnt;

inline bool check(double tar){
    cnt = 0;
    isap.g.Init();
    for(int i = 1; i <= n; i++)
        tmp_arr[++ cnt] = r[i], tmp_arr[++ cnt] = d[i] + tar;
    sort(tmp_arr + 1, tmp_arr + 1 + cnt);
    cnt = unique(tmp_arr + 1, tmp_arr + 1 + cnt) - tmp_arr - 1;
    for(int i = 1; i <= n; i++)
        isap.g.add_edge(s, i, p[i]);
    for(int i = 2; i <= cnt; i++){
        double lst = tmp_arr[i - 1], tim = tmp_arr[i] - lst;
        for(int j = 1; j <= m; j++)
            isap.g.add_edge(n + (i - 2) * m + j, t, j * tim * ss[j]);
        for(int j = 1; j <= n; j++)
            if(r[j] <= lst && d[j] + tar >= tmp_arr[i])
                for(int k = 1; k <= m; k++)
                    isap.g.add_edge(j, n + (i - 2) * m + k, tim * ss[k]);
    }
    return !comp(isap.ISAP(), sum);
}

int main(){
    Main_Init();
    int T = read();
    while(T --){
        n = read(), m = read();
        sum = 0;
        for(int i = 1; i <= n; i++)
            sum += (p[i] = read()), r[i] = read(), d[i] = read();
        for(int i = 1; i <= m; i++)
            ss[i] = read();
        ss[m + 1] = 0;
        int tmp = ss[1];
        sort(ss + 1, ss + 1 + m, greater<int>());
        for(int i = 1; i <= m; i++)
            ss[i] -= ss[i + 1];
        double l = 0, r = 1.0 * sum / tmp, mid;
        while(fabs(r - l) > eps){
            mid = (l + r) / 2.0;
            if(check(mid)) r = mid;
            else l = mid;
        }
        printf("%.5lf\n", mid);
    }
    Main_Init();
    return 0;
}

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

宣传

题面

题解

二分答案+最大流

举个例子

证明