专栏文章

题解：CF1146G Zoning Restrictions

BBpds1110
CF1146G题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miodexcl
此快照首次捕获于
2025/12/02 17:23
3 个月前
此快照最后确认于
2025/12/02 17:23
3 个月前
查看原文
先考虑没有限制的情况。
发现每个位置的高度取值都极少，而位置数也很少，于是考虑，将每个位置的所有高度的取值都拆成 hh 个节点，总的节点数为 nhnh。我们记 ii 位置高度为 jj 对应的节点为 pi,jp_{i, j}。
容易发现，同个位置的相邻高度间连有向边，选定一个高度等价于选择一条该位置上的边。具体地，选择第 ii 个位置，j−1j - 1 的高度，则选择边 (pi−1,j−1,pi−1,j)(p_{i - 1, j - 1}, p_{i - 1, j})，边权为 (j−1)2(j - 1)^2。
钦定两个点 SS 与 TT，连所有 (S,pi,0)(S, p_{i, 0}) 和 (pi,h,T)(p_{i, h}, T)。问题等价于求该有向图的最大割。
考虑如何处理限制的情况，我们需要构造出一些点和边，使得上述求最大割的方法任然成立。
对于每组限制 (l,r,x,c)(l, r, x, c)，对于所有 i∈[l,r]i \in [l, r]，连 (pi,h+1,k)(p_{i, h + 1}, k)。其中 kk 为每组限制各自具有的节点，边权为 −∞- \infty；再连 (k,T)(k, T)，边权为 −c-c。
显然，求最大割也是成立的。因为不可能选择割掉 −∞- \infty，要求满足不连通，只能割掉 (k,T)(k, T) 或者高度满足限制的边。
于是就将问题转化为了如何求一个有向图的最大割。
考虑将所有边权都取相反数，再用最大流跑。因为取相反数后可能会有负数，于是可以加上偏移量。但是对于限制中的 −c-c，取反为 cc 后，显然不用加。
CPP
// Problem: CF1146G Zoning Restrictions
// URL: https://www.luogu.com.cn/problem/CF1146G
// 1000 ms  250 MB

#include <bits/stdc++.h>
#define int long long
using ll = long long; 
using ull = unsigned long long;
using i28 = __int128;
int min(int x, int y) { return x < y ? x : y; }
constexpr int AD = 1919810, inf = 1e14, N = 2e5 + 10, M = 2e6 + 10; 
int S, T, n, h, m, dis[N], nxt[M << 1], head[N], to[M << 1], g[M << 1], cur[N], cnt = 1; 
void addedge(int u, int v, int w) { nxt[++cnt] = head[u], head[u] = cnt, to[cnt] = v, g[cnt] = w; }
void add(int u, int v, int w) { addedge(u, v, w), addedge(v, u, 0); }
bool bfs(int s, int t) {
	for (int i = 1; i <= T; ++i) dis[i] = inf; dis[s] = 0; std::queue <int> q; q.push(s), cur[s] = head[s]; 
	while (!q.empty()) { int u = q.front(); q.pop();
		for (int i = head[u]; i; i = nxt[i]) { int v = to[i];
			if (g[i] > 0 && dis[u] + 1 < dis[v]) {
				dis[v] = dis[u] + 1, q.push(v), cur[v] = head[v]; if (v == t) return 1; 
			}
		}
	}
	return 0; 
}
int dfs(int u, int t, int cur_flow) {
	if (u == t) return cur_flow; int ret = 0; 
	for (int &i = cur[u]; i && cur_flow > 0; i = nxt[i]) { int v = to[i]; 
		if (g[i] > 0 && dis[u] + 1 == dis[v]) {
			int add = dfs(v, t, min(cur_flow, g[i]));
			if (!add) dis[v] = inf;
			g[i] -= add, g[i ^ 1] += add, ret += add, cur_flow -= add; 
		}
	} return ret; 
}
int Max_Flow(int s, int t) { int ret = 0; while (bfs(s, t)) ret += dfs(s, t, inf); return ret; }
signed main() {
	// freopen(".in", "r", stdin), freopen(".out", "w", stdout); 
	std::ios::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr);
	std::cin >> n >> h >> m;
	S = h * n + m + 1, T = S + 1; 
	for (int i = 1; i <= n; ++i) {
		add(S, (i - 1) * h + 1, AD);
		for (int j = 2; j <= h; ++j) add((i - 1) * h + j - 1, (i - 1) * h + j, AD - (j - 1) * (j - 1)); 
		add(i * h, T, AD - h * h); 
	}
	for (int i = 1; i <= m; ++i) {
		int l, r, x, c; std::cin >> l >> r >> x >> c; if (x == h) continue ;
		for (int j = l; j <= r; ++j) add((j - 1) * h + x + 1, n * h + i, inf);
		add(n * h + i, T, c); 
	} int ret = AD * n - Max_Flow(S, T); std::cout << ret << "\n"; 
	return 0; 
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...