Snuke the Phantom Thief

题目链接luogu AGC031E

题目大意

有 n 个特殊点分布在二维平面上每个点有坐标和价值。
你要选一些点总价值是你选的点的价值和。
然后有一些约束横坐标或者纵坐标大于等于或者小于等于某个值的你选了的点的数量不能超过某个数。
要你最大化总价值。

思路

看到范围会感觉可以用费用流做。
不过按着题目的感觉弄会发现一个问题就是你可以算出每个方向上的最严限制然后每个要选的点就要满足多个条件。
但你是很难做到的因为你不能让一条边要么不流要么流满。

所以考虑换一下思路尝试将题目的条件转化再建模。
发现把条件反过来一下也就是一个限制变成你选的前 $k$ 个点或者后 $k$ 个点的横坐标或纵坐标要小于等于或大于等于某个数。
那换句话说我们尝试从一个区间的点的限制规划到一个点的就是第 $k+1$ 个点的横坐标或者纵坐标要大于或者小于某个数。

不过要注意的一点是横纵坐标应该是分开的因为我们这里的第 k 个点在横纵坐标里面可能并不是同一个点是按横坐标或者纵坐标排序得到的第 k 个点。
那我们就有建图的想法了首先我们枚举一个 k 表示我们选多少个点。

然后源点 $S$ 连到左边的 $k$ 个点右边的 $k$ 个点连到汇点 $T$表示选点。
然后你考虑所有的 $n$ 个点进行一个拆点之间的边的费用就是点权。
然后你考虑左边的 $k$ 个点表示按横坐标排序右边的 $k$ 个点表示按纵坐标排序。
那你一个点 $x$ 可以跟左边或者后边的某个点 $y$ 连接就是要它处在这个位置的时候可以满足我们的限制。
这个限制我们可以预处理出来就是按前面的确立关系然后前缀和后缀和一下

然后跑费用流就行。
不过要注意的是它这里是要费用最大所以把费用改成小 $inf-v$然后费用流加的时候就是流量乘小 $inf-di{s}_T$

代码

#include<queue>
#include<cstdio>
#include<iostream>
#define ll long long
#define INF 0x3f3f3f3f3f3f3f3f

using namespace std;

const ll N = 85;
const ll M = 350;
const ll inf = 1e15;
struct Dian {
	ll x, y, op, z;
}a[N], b[M];
struct node {
	ll x, cst, to, nxt, op;
}e[N * M * 2 * 2];
ll n, m, S, T, le[(N + M) * 2], KK;
ll L[N], R[N], U[N], D[N], ans;

void add(ll x, ll y, ll z, ll cst) {
	e[++KK] = (node){z, cst, y, le[x], KK + 1}; le[x] = KK;
	e[++KK] = (node){0, -cst, x, le[y], KK - 1}; le[y] = KK;
}

ll deg[(N + M) * 2], lee[(N + M) * 2];
ll dis[(N + M) * 2];
bool in[(N + M) * 2];
queue <ll> q;

bool SPFA() {
	for (ll i = 1; i <= T; i++) deg[i] = in[i] = 0, dis[i] = INF, lee[i] = le[i];
	while (!q.empty()) q.pop(); ll chk = dis[T];
	q.push(S); dis[S] = 0; deg[S] = 1; in[S] = 1;
	while (!q.empty()) {
		ll now = q.front(); q.pop();
		for (ll i = le[now]; i; i = e[i].nxt)
			if (dis[e[i].to] > dis[now] + e[i].cst && e[i].x) {
				dis[e[i].to] = dis[now] + e[i].cst;
				deg[e[i].to] = deg[now] + 1;
				if (!in[e[i].to]) {
					in[e[i].to] = 1; q.push(e[i].to);
				}
			}
		in[now] = 0;
	}
	return dis[T] != chk;
}

ll dfs(ll now, ll sum) {
	if (now == T) return sum;
	ll go = 0;
	for (ll &i = lee[now]; i; i = e[i].nxt)
		if (e[i].x & dis[e[i].to] == dis[now] + e[i].cst && deg[e[i].to] == deg[now] + 1) {
			ll this_go = dfs(e[i].to, min(sum - go, e[i].x));
			if (this_go) {
				e[i].x -= this_go; e[e[i].op].x += this_go;
				go += this_go; if (go == sum) return go;
			}
		}
	deg[now] = -1; return go;
}

ll Dinic() {
	ll re = 0, cnt = 0;
	while (SPFA()) {
		ll x = dfs(S, INF);
		re += x * (inf - dis[T]);
	}
	return re;
}

ll work(ll k) {
	S = (n + k) * 2 + 1, T = S + 1;
	for (ll i = 1; i <= k; i++) {
		add(S, i, 1, 0); add(i + k, T, 1, 0);
	}
	for (ll i = 1; i <= n; i++) {
		for (ll j = 1; j <= k; j++) {
			if (L[j] <= a[i].x && a[i].x <= R[k - j + 1]) add(j, 2 * k + i, 1, 0);
			if (D[j] <= a[i].y && a[i].y <= U[k - j + 1]) add(2 * k + n + i, j + k, 1, 0);
		}
		add(2 * k + i, 2 * k + n + i, 1, inf - a[i].z);
	}
	
	ll re = Dinic();
	for (ll i = 1; i <= T; i++) le[i] = 0; KK = 0;
	return re;
}

int main() {
	scanf("%lld", &n);
	for (ll i = 1; i <= n; i++) {
		scanf("%lld %lld %lld", &a[i].x, &a[i].y, &a[i].z);
	}
	scanf("%lld", &m);
	for (ll i = 0; i <= n + 1; i++) R[i] = U[i] = inf;
	for (ll i = 1; i <= m; i++) {
		char c = getchar(); while (c != 'L' && c != 'R' && c != 'U' && c != 'D') c = getchar();
		if (c == 'L') b[i].op = 0; if (c == 'R') b[i].op = 1; if (c == 'D') b[i].op = 2; if (c == 'U') b[i].op = 3;
		scanf("%lld %lld", &b[i].x, &b[i].y);
		if (b[i].op == 0) L[b[i].y + 1] = max(L[b[i].y + 1], b[i].x + 1);
		if (b[i].op == 1) R[b[i].y + 1] = min(R[b[i].y + 1], b[i].x - 1);
		if (b[i].op == 2) D[b[i].y + 1] = max(D[b[i].y + 1], b[i].x + 1);
		if (b[i].op == 3) U[b[i].y + 1] = min(U[b[i].y + 1], b[i].x - 1);
	}
	for (ll i = 1; i <= n; i++) L[i] = max(L[i], L[i - 1]), R[i] = min(R[i], R[i - 1]), D[i] = max(D[i], D[i - 1]), U[i] = min(U[i], U[i - 1]);
	//预处理关系
	
	for (ll i = 1; i <= n; i++) ans = max(ans, work(i));
	printf("%lld", ans);
	
	return 0;
}