Visits: 236

CF704D Captain America

题意

• 平面上有 $n$ 个点，第 $i$ 个点的坐标为 $(x_i, y_i)$。
• 每个点都要被涂色，涂成红色需要 $r$ 元，涂成蓝色需要 $b$ 元。
• 另外有 $m$ 个限制，每个限制有两种可能：
  • 1 l d 表示在直线 $x = l$ 上，涂成两种颜色的点的数量之差不超过 $d$。
  • 2 l d 表示在直线 $y = l$ 上，涂成两种颜色的点的数量之差不超过 $d$。
• 要求构造出一种涂色方案使得满足所有限制且总花费最少，或判断无法构造。
• $n,m \le 10^5$。

题解

不妨设 $r\le b$，否则可以交换 $r,b$，那么我们要尽可能的多涂红色。

将坐标离散化，建立二分图，左部点 $x_i$ 表示横坐标 $x_i$，右部点 $y_i$ 表示纵坐标 $y_i$。

对于每条线，设 $d$ 表示这条线上最紧的限制，$c$ 表示这条线上的点的个数，则红点数 $k$ 要满足 $\lceil \frac{c-d}2 \rceil \le k \le \lfloor \frac{c+d}2 \rfloor$。如果这条线为 $x = i$，则从源点 $S$ 向 $x_i$ 连一条下界为 $\lceil \frac{c-d}2 \rceil$ 上界为 $\lfloor \frac{c+d}2 \rfloor$ 的边；如果这条线为 $y = i$，则从 $x_i$ 向汇点 $T$ 连一条下界为 $\lceil \frac{c-d}2 \rceil$ 上界为 $\lfloor \frac{c+d}2 \rfloor$ 的边。

对于每个点 $(x_i,y_i)$，从 $x_i$ 向 $y_i$ 连一条下界为 $0$ 上界为 $1$ 的边，这条边有流量则意味着这个点涂红色，否则涂蓝色。

则这张图的一个可行流对应着原问题的一组解，而最大流对应着原问题的最优解，因此跑一遍有源汇上下界最大流即可。

代码

namespace Dinic {
    const int N = 2e5 + 7, M = 1e6 + 7;
    const ll inf = 1e18;
    int n, m, S, T, h[N], hi[N], e[M], t[M], tot = 1, d[N];
    ll mxf, f[M];
    inline void add(int x, int y, ll z, int o = 1) {
        e[++tot] = y, f[tot] = z, t[tot] = h[x], h[x] = tot;
        if (o) add(y, x, 0, 0);
    }
    inline bool bfs() {
        for (int i = 1; i <= n; i++) d[i] = 0;
        queue<int> q;
        q.push(S), d[S] = 1;
        while (q.size()) {
            int x = q.front();
            q.pop();
            for (int i = h[x]; i; i = t[i]) {
                int y = e[i];
                ll z = f[i];
                if (d[y] || !z) continue;
                q.push(y), d[y] = d[x] + 1;
                if (y == T) return 1;
            }
        }
        return 0;
    }
    ll dinic(int x, ll nwf) {
        if (x == T) return nwf;
        ll rst = nwf;
        for (int &i = hi[x]; i; i = t[i]) {
            int y = e[i];
            ll z = f[i];
            if (d[y] != d[x] + 1 || !z) continue;
            ll k = dinic(y, min(z, rst));
            if (!k) d[y] = 0;
            else f[i] -= k, f[i^1] += k, rst -= k;
            if (!rst) break;
        }
        return nwf - rst;
    }
    inline void main() {
        while (bfs()) {
            for (int i = 1; i <= n; i++) hi[i] = h[i];
            ll now;
            while ((now = dinic(S, inf))) mxf += now; 
        }
    }
}

namespace no_ok_flow {
    const int N = 2e5 + 7;
    ll d[N], s;
    inline void add(int x, int y, ll l, ll r) {
        Dinic::add(x, y, r - l), d[y] += l, d[x] -= l;
    }
    inline bool main() {
        Dinic::S = Dinic::n + 1, Dinic::T = Dinic::n + 2;
        for (int i = 1; i <= Dinic::n; i++)
            if (d[i] > 0) Dinic::add(Dinic::S, i, d[i]), s += d[i];
            else if (d[i] < 0) Dinic::add(i, Dinic::T, -d[i]);
        Dinic::n += 2, Dinic::main(), Dinic::n -= 2;
        return Dinic::mxf == s;
    }
}

namespace yes_max_flow {
    const ll inf = 1e18;
    int S, T;
    inline bool main() {
        no_ok_flow::add(T, S, 0, inf);
        if (!no_ok_flow::main()) return 0;
        Dinic::S = S, Dinic::T = T, Dinic::mxf = 0;
        return Dinic::main(), 1;
    }
}

const int N = 1e5 + 7;
int n, m, b[2], t;
char c[2];
pi p[N];
map<int, int> cx, cy, fx, fy, dx, dy;

int main() {
    rd(n), rd(m), rd(b[0]), rd(b[1]);
    c[0] = 'r', c[1] = 'b';
    if (b[0] > b[1]) swap(b[0], b[1]), swap(c[0], c[1]);
    for (int i = 1; i <= n; i++)
        rd(p[i].fi), rd(p[i].se),
        ++cx[p[i].fi], ++cy[p[i].se],
        fx[p[i].fi] = fy[p[i].se] = 0;
    for (pi o : cx) dx[o.fi] = o.se;
    for (pi o : cy) dy[o.fi] = o.se;
    for (pi o : fx) fx[o.fi] = ++t;
    for (pi o : fy) fy[o.fi] = ++t;
    for (int i = 1; i <= n; i++)
        no_ok_flow::add(fx[p[i].fi], fy[p[i].se], 0, 1);
    for (int i = 1, o, x, y; i <= m; i++) {
        rd(o), rd(x), rd(y);
        if (o == 1 && dx.find(x) != dx.end()) dx[x] = min(dx[x], y);
        if (o == 2 && dy.find(x) != dy.end()) dy[x] = min(dy[x], y);
    }
    for (pi o : fx) {
        int c = cx[o.fi], d = dx[o.fi];
        int l = (c - d) / 2 + ((c ^ d) & 1), r = (c + d) / 2;
        if (l > r) return print(-1), 0;
        no_ok_flow::add(t + 1, o.se, l, r);
    }
    for (pi o : fy) {
        int c = cy[o.fi], d = dy[o.fi];
        int l = (c - d) / 2 + ((c ^ d) & 1), r = (c + d) / 2;
        if (l > r) return print(-1), 0;
        no_ok_flow::add(o.se, t + 2, l, r);
    }
    yes_max_flow::S = ++t, yes_max_flow::T = ++t, Dinic::n = t;
    if (!yes_max_flow::main()) return print(-1), 0;
    ll ans = 0;
    string s = "";
    for (int i = 1, j = 2; i <= n; i++, j += 2)
        ans += b[Dinic::f[j]], s += c[Dinic::f[j]];
    print(ans), prints(s);
    return 0;
}