【题解】CF 704D Captain America

Problem

有 $n$ 个点在平面上,可以被染成红色或者蓝色,费用分别为 $r,b$

有 $m$ 个限制,共两种:

  1. 第 $i$ 行红蓝点之差不超过 $d$
  2. 第 $i$ 列红蓝点之差不超过 $d$

寻找染色总费用最少的方案

Thought

绝对值不好做,不如将当前所有点变为红点,然后考虑需要将每一行每一列多少个点变为蓝点

考虑一个限制为第 $i$ 列的红蓝点之差不超过 $d$,假设当前列有 $k$ 个节点,那么被染成蓝点的个数应该在 $\left[\left\lceil\frac{k-d}{2}\right\rceil,\left\lfloor\frac{k+d}{2}\right\rfloor\right]$ 范围内,这个可以很简单的用有上下界网络流的流量进行限制
行限制同理

同时,假设蓝点费用比红点高,那么我们需要使得被染色的点尽量的少,反之尽量的多
即有源汇有上下界最大/小流问题,可以转化为无源汇有上下界最大/小流问题

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 = 100010;
int s, t, S, T, cntNode;
int d[N << 1], f[N << 1], cur[N << 1];
struct Edge {
    int t, n, f;
}e[30 * N];
int head[N << 1], Etot = 1;
int n, m, r, b;
struct Node {
    int x, y;
}p[N];
int X[N], Y[N];

bool visx[N], visy[N];
int XX[N], YY[N];
int fr[N];
int H[N], L[N];
ll sum, ans, F;

void addedge(int u, int v, int w) {
    e[++ Etot] = {v, head[u], w};
    head[u] = Etot;
    e[++ Etot] = {u, head[v], 0};
    head[v] = Etot;
}
int dfs(int x, int flow) {
    if(x == t) return flow;
    int use = 0;
    for(int i = cur[x]; i; i = e[i].n) {
        cur[x] = i;
        if(!e[i].f || d[e[i].t] + 1 != d[x]) continue;
        int 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;
}
int FLOW[N << 1];
int main() {
    n = read(); m = read();
    r = read(); b = read();
    sum = 1ll * r * n;
    for(int i = 1; i <= n; ++ i) {
        X[i] = p[i].x = read();
        Y[i] = p[i].y = read();
    }
    sort(X + 1, X + n + 1);
    sort(Y + 1, Y + n + 1);
    int difx = unique(X + 1, X + n + 1) - X - 1;
    int dify = unique(Y + 1, Y + n + 1) - Y - 1;
    cntNode = difx + dify;
    S = ++ cntNode; T = ++ cntNode;
    s = ++ cntNode; t = ++ cntNode;
    for(int i = 1; i <= n; ++ i) {
        p[i].x = lower_bound(X + 1, X + difx + 1, p[i].x) - X;
        p[i].y = lower_bound(Y + 1, Y + dify + 1, p[i].y) - Y;
        ++ H[p[i].x]; ++ L[p[i].y];
        fr[i] = Etot + 1;
        addedge(p[i].x, difx + p[i].y, 1);
    }
    for(int i = 1; i <= difx; ++ i)
        XX[i] = H[i];
    for(int i = 1; i <= dify; ++ i)
        YY[i] = L[i];
    for(int i = 1; i <= m; ++ i) {
        int t = read(), l = read(), d = read();
        if(t == 1) {
            int pos = lower_bound(X + 1, X + difx + 1, l) - X;
            if(X[pos] != l) continue;
            else l = pos;
            XX[l] = min(XX[l], d);
        }
        else {
            int pos = lower_bound(Y + 1, Y + dify + 1, l) - Y;
            if(Y[pos] != l) continue;
            else l = pos;
            YY[l] = min(YY[l], d);
        }
    }
    for(int i = 1; i <= difx; ++ i) {
        int low = (H[i] - XX[i] + 1) / 2;
        int up = (H[i] + XX[i]) / 2;
        if(up < low) {
            puts("-1");
            return 0;
        }
        FLOW[S] -= low;
        FLOW[i] += low;
        addedge(S, i, up - low);
    }
    for(int i = 1; i <= dify; ++ i) {
        int low = (L[i] - YY[i] + 1) / 2;
        int up = (L[i] + YY[i]) / 2;
        if(up < low) {
            puts("-1");
            return 0;
        }
        FLOW[difx + i] -= low;
        FLOW[T] += low;
        addedge(difx + i, T, up - low);
    }
    for(int i = 1; i <= cntNode; ++ i) {
        if(FLOW[i] > 0) {
            addedge(s, i, FLOW[i]);
            F += FLOW[i];
        }
        else if(FLOW[i] < 0)
            addedge(i, t, - FLOW[i]);
    }
    addedge(T, S, 0x3f3f3f3f);
    f[0] = cntNode;
    while(d[s] < cntNode)
        ans += dfs(s, 1 << 30);
    if(ans != F) puts("-1");
    else {
        ans = e[Etot].f;
        memset(d, 0, sizeof(d));
        memset(f, 0, sizeof(f));
        memset(cur, 0, sizeof(cur));
        f[0] = cntNode;
        cntNode -= 2;
        e[Etot].f = 0; e[Etot ^ 1].f = 0;
        for(int i = head[s]; i; i = e[i].n) {
            e[i].f = 0;
            e[i ^ 1].f = 0;
        }
        for(int i = head[t]; i; i = e[i].n) {
            e[i].f = 0;
            e[i ^ 1].f = 0;
        }
        if(r > b) {
            s = S; t = T;
            while(d[s] < cntNode)
                ans += dfs(s, 1 << 30);
            sum += 1ll * ans * (b - r);
        }
        else {
            s = T; t = S;
            while(d[s] < cntNode)
                ans -= dfs(s, 1 << 30);
            sum += 1ll * ans * (b - r);
        }
        printf("%lld\n", sum);
        for(int i = 1; i <= n; ++ i)
            if(e[fr[i]].f)
                putchar('r');
            else
                putchar('b');
    }
    return 0;
}
Comments

添加新评论