题解 CF704D 【Captain America】

> [CF704D Captain America](https://codeforces.com/contest/704/problem/D) ## 题意 - 平面上有 $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$ 的边，**这条边有流量则意味着这个点涂红色，否则涂蓝色**。 则这张图的一个可行流对应着原问题的一组解，而最大流对应着原问题的最优解，因此跑一遍**有源汇上下界最大流**即可。 ## 代码 ```cpp 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; } ```