题解 P3347 【[ZJOI2015]醉熏熏的幻想乡】

· · 题解

可以在我的博客食用
抱歉上次链接挂错了
题面
不得不说,浙江神队选拔赛真是年年毒瘤
首先你需要有一点导数的知识,否则可能看不懂
第一问很简单,建个图跑个最大流就好了(如果这都不会还敢来肝zjoi???)
第二问

  1. 有一个很fAKe的想法:
    因为费用不是一次函数,而是二次函数,并且我们观察到a,b>=0
    所以我先想到的是把每个酿酒点的费用强行离散,就是分成一个个区间,然后源点向每个酿酒点连很多条边,再跑费用流
    因为导函数单调不降,所以理论上是可以做到一定精度的
    然而我们观察到毒瘤出题人要求输出分数

  2. 让误差降为0???
    显然分的越细误差越小
    考虑分的份数无限趋于0
    此时费用即为导数
    然后就可以开个集合维护当前单位费用最小的酿酒点
    然后二分出当单位费用涨到多少时,集合内点会变化(要么是有新点加入,要么是有一个点跑满流)
    然后更新集合并进行下一轮操作
    然而二分还是只能做到一定精度(貌似乘上一个奥妙重重的系数可以二分整数,但我不知道是不是对的,而且复杂度好像是假的)

  3. 正解! 观察一下解法2,就会发现当集合内点不变时,产酒量(当前流量)和费用呈线性关系,并且当集合内点变化时,费用的一次函数会发生变化，最多变化2 n次

所以搞一个函数y = f(x)表示单位费用(导数)不超过x时,最大流是多少
那么f(x)可以被分成若干段,每段均为一次函数,最多2n=O(n)段
然后可以用类似积分的方式搞出最小费用 考虑怎么搞出这个函数
如果只有二次函数的费用,那么f(x)会形成一个类似上凸壳的图像
然后考虑分治,每次求出最左一次函数和最右一次函数的交点，如果再图像上则该点是区间内唯一断点，否则递归处理两个子区间
然后考虑一次函数
发现b只会是0, 1, 2, 3(详细数据范围见bzoj)
只要强行设1, 2, 3为断点即可
记得加上左右边界的f(x)之差(见代码) 复杂度O(n\times网络流)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const db feps = 1e-11, eps = 1e-9;
inline ll gcd(ll a, ll b) {
    return a == 0 || b == 0 ? a | b : gcd(b, a % b);
}
struct frac {
    ll a, b; //仔细看题发现要开ll
    inline frac(ll _a = 0, ll _b = 1) {
        int g = gcd(_a, _b);
        a = _a / g, b = _b / g;
    }
    friend inline frac operator + (frac a, frac b) {
        return frac(a.a * b.b + a.b * b.a, a.b * b.b);
    }
    friend inline frac operator - (frac a, frac b) {
        return frac(a.a * b.b - a.b * b.a, a.b * b.b);
    }
    friend inline frac operator * (frac a, frac b) {
        return frac(a.a * b.a, a.b * b.b);
    }
    friend inline frac operator / (frac a, frac b) {
        return frac(a.a * b.b, a.b * b.a);
    }
    inline operator db () {
        return 1.0l * a / b;
    }
};
int dis[210], s, t;
int a[110], b[110], c[110], d[110], ed[110][110];
struct edge {
    db f;
    int v, nxt;
} e[3010];
int tot, head[210], cur[210];
int n, m;
inline void addedge(int u, int v, db c) {
    e[++tot] = edge{c, v, head[u]};
    head[u] = tot;
    e[++tot] = edge{0, u, head[v]};
    head[v] = tot;
}
inline int bfs() {
    queue<int> q;
    memset(dis, -1, sizeof dis);
    dis[s] = 0;
    q.push(s);
    memcpy(cur, head, sizeof head);
    while(!q.empty()) {
        int now = q.front();
        q.pop();
        for(int i = head[now]; i; i = e[i].nxt) {
            if(~dis[e[i].v] || e[i].f < feps) continue;
            dis[e[i].v] = dis[now] + 1;
            q.push(e[i].v);
        }
    }
    return dis[t] != -1;
}
inline db dfs(int now, db limit) {
    if(now == t) return limit;
    db ans = 0;
    for(int &i = cur[now]; i; i = e[i].nxt) {
        if(e[i].f < feps || dis[e[i].v] != dis[now] + 1) continue;
        db lala = dfs(e[i].v, min(limit, e[i].f));
        limit -= lala, ans += lala;
        e[i].f -= lala, e[i ^ 1].f += lala;
        if(limit < feps) return ans;
    }
    return ans;
}
inline pair<frac, frac> dinic(db lambda) {
    tot = 1;
    memset(head, 0, sizeof head);
    for(int i = 1; i <= n; i++) {
        if(a[i] == 0) {
            if(b[i] < lambda) addedge(s, i, c[i]);
        }
        else {
            db w = (lambda - b[i]) / 2 / a[i];
            if(w > feps) addedge(s, i, min(1.0 * c[i], w));
        }
    }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++) if(ed[i][j]) addedge(i, j + n, 1e9);
    for(int i = 1; i <= m; i++) addedge(i + n, t, d[i]);
    while(bfs()) dfs(s, 1e9);
    frac K, B;
    for(int i = 1; i <= n; i++) {
        if(dis[i] == -1) {
            if(a[i] == 0) {
                if(b[i] < lambda) B = B + frac(c[i]);
            }
            else {
                if(b[i] > lambda) B = B + frac();
                else if(a[i] * 2 * c[i] + b[i] > lambda)
                    K = K + frac(1, a[i] * 2), B = B - frac(b[i], a[i] * 2);
                else B = B + frac(c[i]);
            }
        }
    }
    for(int i = 1; i <= m; i++) if(dis[i + n] != -1) B = B + frac(d[i]);
    return make_pair(K, B);
}                                                                      //dinic板子
vector<pair<frac, frac> > v;
inline void solve(pair<frac, frac> fl, pair<frac, frac> fr) {          //分治找断点
    if(fl.first == fr.first && fl.second == fr.second) return;
    frac px = (fl.second - fr.second) / (fr.first - fl.first);
    pair<frac, frac> fml = dinic((db)px - eps), fmr = dinic((db)px + eps);
    if(fmr.first == fr.first && fmr.second == fr.second) {
        v.push_back(make_pair(px, fml.second + fml.first * px));
    } else {
        solve(fl, fml);
        solve(fmr, fr);
    }
}
int main() {
    scanf("%d%d", &n, &m);
    s = 0, t = n + m + 1;
    for(int i = 1; i <= n; i++) scanf("%d%d%d", a + i, b + i, c + i);
    for(int i = 1; i <= m; i++) scanf("%d", d + i);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++) scanf("%d", &ed[i][j]);
    frac ans, sum;
    cout << (sum = dinic(1e9).second).a;//第一问
    v.push_back(make_pair(frac(), 0));
    for(int i = 1; i <= 3; i++) {
        auto l = dinic(i - 1 + eps), r = dinic(i - eps);
        solve(l, r);
        v.push_back(make_pair(frac(i), r.second + frac(i) * r.first));
    }
    solve(dinic(3 + eps), dinic(1e9));//找断点
    for(int i = 1; i < v.size(); i++) {
        auto l = dinic((db)v[i].first - eps), r = dinic((db)v[i].first + eps), _l = dinic((db)v[i - 1].first + eps);//std=c++11(滑稽
        ans = ans + v[i].first * ((r.first - l.first) * v[i].first + r.second - l.second);
        ans = ans + (v[i].second - v[i - 1].first * _l.first - _l.second) * frac(1, 2) * (v[i].first + v[i - 1].first);//积分
    }
    if(ans.a < 0) ans.a = -ans.a, ans.b = -ans.b;
    return cout << ans.a << '/' << ans.b << endl, 0;
}