CF704D Captain America 题解

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;
}