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

· · 题解

myblog: http://blog.csdn.net/miaomiao\_ymxl/article/details/54849702

思路：

网络流好题

应该容易想到二分答案和离散化奶酪的时间点

先考虑朴素的建图，也就是不考虑每个时刻可以有多只老鼠在不同的小时刻吃同一个奶酪

1.我们将源点每个奶酪链流量为p[i]的边

2.然后把每只老鼠的每个时间段拆为一个点，再将其与对应的奶酪连边，流量为这只老鼠可以在这个时间段吃多少奶酪

3.所有的老鼠向汇点连边，无限流量

然而题目有限制，每个时刻可以有多只老鼠在不同的小时刻吃同一个奶酪，做法很巧妙，我们可以对老鼠的速度再进行拆点，把s[]从大到小排序然后与下一个作差，如”9 6 2 1” -> “3 4 1 1”，然后再将其与汇点连边的流量改为（rat为老鼠编号，dur为时间段大小，s为作差后的数组）rat*s[rat]*dur即可

为什么呢？

可以发现速度进行过如此处理之后，

9 = 3+4+1+1
6 = 4+1+1
2 = 1+1
1 = 1
9+6+2+1 = 3*1 + 4*2 + 1*3 + 1*4

(下面所有的s数组均为作差后的数组) 1.所以，当我们把老鼠点到汇点的流量限制设为rat*s[rat]*dur后，对于每一只老鼠，它‘吃’的量不超过实际可以‘吃’的量。（上述式子解释了，实际包括编号比它小的老鼠的吃的量）

2.每个老鼠点与奶酪的连边为s[rat]*dur，这样可以保证每只老鼠实际不可以超过自己这段时间可以吃的奶酪。

3.（对于第2点的解释）实际这段时间奶酪被吃的量不超过最快的老鼠的速度在这个时间段可以吃的量，如果每只老鼠在2点所述的边满流，那么实际相当于吃的最快的老鼠吃了这一整个时间段。而任何其它的情况均可以用别的老鼠凑出来，且由于第一点不会不合法

最后，每次二分答案，重新构图跑最大流，检查是否满流即可。

代码：

‘’

//miaomiao 2017.2.3
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define pb push_back
#define Set(a, v) memset(a, v, sizeof(a))
#define For(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define MN (30+5)
#define N (3000+5)
#define eps (1e-6)
struct Edge{
    int from, to;
    double cap, flow;
};
struct Dinic{
    vector<int> G[N];
    vector<Edge> edges;
    int m, s, t;
    int cur[N], d[N]; 
    void init(){
        For(i, 0, N-1) G[i].clear();
        edges.clear(); 
    }
    void AddEdge(int u, int v, double cap){
        edges.pb((Edge){u, v, cap, 0});    
        edges.pb((Edge){v, u, 0, 0});
        m = edges.size();
        G[u].pb(m-2); G[v].pb(m-1);
    }
    bool Bfs(){
        queue<int> q;
        q.push(s); Set(d, 0);
        d[s] = 1; 
        int now;
        while(!q.empty()){
            now = q.front(); q.pop();
            For(i, 0, G[now].size()-1){
                Edge &e = edges[G[now][i]];
                if(!d[e.to] && e.cap-e.flow > eps){
                    d[e.to] = d[now]+1;
                    q.push(e.to);
                }
            }
        }
        return d[t];
    }
    double dfs(int now, double Mint){
        if(Mint < eps || now == t) return Mint;
        double f;
        double ret = 0.0;
        for(int &i = cur[now]; i < G[now].size(); i++){
            Edge &e = edges[G[now][i]];
            if(d[e.to]==d[now]+1 && (f=dfs(e.to, fmin(Mint, e.cap-e.flow)))>eps){
                e.flow += f; Mint -= f;
                edges[G[now][i]^1].flow -= f;
                ret += f;
                if(Mint < eps) return ret;
            }
        }
        return ret;
    }
    double Maxflow(){
        double ret = 0.0;
        while(Bfs()){
            Set(cur, 0);
            ret += dfs(s, (1LL<<60)*1.0);
        }
        return ret;
    }
}Din;
int n, m;
double L, R, rp[MN], rr[MN], rd[MN], rs[MN], Ti[MN*2];
void solve(){
    double mid, la, sum = 0;
    int pn;
    For(i, 1, n) sum += rp[i];
    while(R-L > eps){
        mid = (L+R)/2.0;
        Din.init();
        For(i, 1, n) Din.AddEdge(0, i, rp[i]);
        For(i, 1, n){
            Ti[2*i-1] = rr[i]; Ti[2*i] = rd[i]+mid;            
        }
        sort(Ti+1, Ti+2*n+1);
        Din.s = 0; Din.t = m*2*n+n+1; pn = n;
        For(rat, 1, m){
            la = Ti[1];
            For(i, 2, 2*n){
                if(Ti[i]-la < eps) continue;
                ++pn; Din.AddEdge(pn, Din.t, rat*rs[rat]*(Ti[i]-la));
                For(j, 1, n)
                    if(rr[j]-la < eps && (rd[j]+mid)-Ti[i] > -eps)
                        Din.AddEdge(j, pn, rs[rat]*(Ti[i]-la));
                la = Ti[i];
            }
        }
        if(sum-Din.Maxflow() < eps) R = mid;
        else L = mid;
    }
    printf("%lf\n", L);
}
int main(){
    int T;
    double tot;
    scanf("%d", &T);
    while(T--){
        tot = 0.0;
        scanf("%d%d", &n, &m);
        For(i, 1, n) scanf("%lf%lf%lf", &rp[i], &rr[i], &rd[i]), tot += rp[i];
        For(i, 1, m) scanf("%lf", &rs[i]); sort(rs+1, rs+m+1, greater<int>());
        R = tot/rs[1] + 1.0; L = 0;
        For(i, 1, m-1) rs[i] -= rs[i+1];
        solve();
    }
    return 0;
}
‘’