自动搬运

查看原文

来自洛谷，原作者为

	CaoXian 这是我初一的成就，也是我最后的成就，几年学习终究是证明了自己的上限

搬运于2025-08-24 22:10:58，当前版本为作者最后更新于2024-01-10 18:51:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

最小割。

“有可能有两个坐标描述同一个单元”这一点很麻烦，注意到如果 $x$ 坐标、$y$ 坐标和 $z$ 坐标各增加 $1$ 那么它描述的单元不变，所以将三维转化为二维 $(x, y, z) \to (x - z, y - z)$，并且坐标也有唯一性了。

对于 a 共振，产生共振的三个单元中一定有一个是能量源单元，并且坐标数值之和在模 $3$ 的意义下 $0$，$1$，$2$ 正好各出现一次，这一点可以用鸽巢原理证明。

对于 b 共振，我们会发现它也有类似的情况。

于是直接将 a 共振和 b 共振一起考虑，所以产生共振的条件是：存在三个连通的单元，位于“中间”位置的单元的坐标数值之和模 $3$ 为 $0$，位于“两边”的单元的坐标数值之和模 $3$ 分别为 $1$ 和 $2$。

考虑如何消除共振。

按照上面描述的形式，将坐标数值之和模 $3$ 为 $2$ 的单元看作共振组合的第一个单元，模 $3$ 为 $0$ 的单元看作第二个单元，模 $3$ 为 $1$ 的单元看作第三个单元。

在它们之间依次连接有向边（$2 \to 0, 0 \to 1$），如果某个坐标数值之和模 $3$ 为 $2$ 的单元可以通过有向边走到模 $3$ 为 $1$ 的单元，那么肯定就会有一个共振组合。

而消除一个共振组合只需将其中一个单元删除即可，而题目要求剩下的单元价值总和最大，所以要贪心地删除其中价值最小的单元。

但是一个单元可能出现在多个共振组合中，简单的贪心就不起作用了。

而“贪心地删除三个单元中价值最小的单元”这样的描述很像最小割。如果把最小割当作一种反悔贪心来做的话就可以很好地处理共振组合“重叠”的情况了。

具体地，将每个单元拆点，分别为入点和出点，在其间连接一条容量为其价值的边。从坐标数值之和模 $3$ 为 $2$ 的单元向与其相邻的坐标数值之和模 $3$ 为 $0$ 的单元连接一条容量为 $\infty$ 的边，模 $3$ 为 $0$ 的点再向模 $3$ 为 $1$ 的点连边。

建立源点和汇点，源点向每个坐标数值之和模 $3$ 为 $2$ 的点连一条容量为 $\infty$ 的边，每个坐标数值之和模 $3$ 为 $1$ 的点向汇点连一条容量为 $\infty$ 的边。

跑最小割，此时被割掉的边只可能是每个点拆点过后在其间连的边（其余的边容量都为 $\infty$ 不可能被割），这就对应了删除单元格的情况。

跑完最小割后将满流的边删去，源点和汇点不连通，这也对应了不存在共振的情况。

对于存点，因为复杂度瓶颈在于 Dinic 的 $\mathcal{O}(n^{2}m)$，所以直接用 map 偷懒就行。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using flow_type = ll;
constexpr int inf = 1 << 30;
int St, Ed;
struct edge {
	int to;
	flow_type c;
	int pos;
	edge(int To = 0, flow_type C = 0, int Pos = 0): to(To), c(C), pos(Pos) {}
};
vector<edge> g[100005];
void add_edge(int from, int to, flow_type c, bool directed = true) {
	// cerr << "from " << from << " to " << to << " with " << c << '\n';
	if(!c) return;
	g[from].push_back(edge(to, c));
	g[to].push_back(edge(from, directed ? 0 : c));
	g[from].back().pos = g[to].size() - 1;
	g[to].back().pos = g[from].size() - 1;
}
namespace Dinic {
	int dep[100005], cur[100005];
	queue<int> q;
	bool bfs(int s, int t) {
		fill(dep + St, dep + 1 + Ed, 0);
		dep[s] = 1;
		q.push(s);
		int now;
		while(!q.empty()) {
			now = q.front();
			q.pop();
			for(const auto& i : g[now]) {
				if(!dep[i.to] && i.c) {
					dep[i.to] = dep[now] + 1;
					q.push(i.to);
				}
			}
		}
		return dep[t];
	}
	flow_type dfs(int now, flow_type flw, const int& t) {
		if(now == t) return flw;
		flow_type rest = flw, f;
		const int len = (int)g[now].size();
		while(cur[now] < len) {
			auto& i = g[now][cur[now]];
			if(dep[i.to] == dep[now] + 1 && i.c) {
				f = dfs(i.to, min(i.c, rest), t);
				if(!f) dep[i.to] = 0;
				i.c -= f;
				g[i.to][i.pos].c += f;
				rest -= f;
				if(!rest) break;
			}
			++cur[now];
		}
		return flw - rest;
	}
	flow_type Dinic(int s, int t) {
		flow_type flow = 0;
		while(bfs(s, t)) {
			fill(cur + St, cur + 1 + Ed, 0);
			flow += dfs(s, inf, t);
		}
		return flow;
	}
}
constexpr int dx[] = {-1, -1, 0, 1, 1, 0};
constexpr int dy[] = {-1, 0, 1, 1, 0, -1};
map<pair<int, int>, ll> mp;
map<pair<int, int>, int> id;
int n, s, t, cnt, x, y, z, c, _x, _y;
ll sum;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	while(n--) {
		cin >> x >> y >> z >> c;
		x -= z;
		y -= z;
		if(((x + y) % 3 + 3) % 3) c *= 10;
		else c *= 11;
		sum += c;
		mp[make_pair(x, y)] += c;
	}
	s = ++cnt, t = ++cnt;
	for(const auto& i : mp) {
		id[i.first] = ++cnt;
		++cnt;
		add_edge(cnt - 1, cnt, i.second);
	}
	for(const auto& i : mp) {
		x = i.first.first, y = i.first.second, c = i.second;
		if(((x + y) % 3 + 3) % 3 == 0 || ((x + y) % 3 + 3) % 3 == 2) {
			for(int j = 0; j < 6; ++j) {
				_x = x + dx[j], _y = y + dy[j];
				if(((x + y) % 3 + 3 + 1) % 3 == ((_x + _y) % 3 + 3) % 3) {
					add_edge(id[make_pair(x, y)] + 1, id[make_pair(_x, _y)], inf);
				}
			}
		}
		if(((x + y) % 3 + 3) % 3 == 2) {
			add_edge(s, id[make_pair(x, y)], inf);
		}
		if(((x + y) % 3 + 3) % 3 == 1) {
			add_edge(id[make_pair(x, y)] + 1, t, inf);
		}
	}
	St = 1, Ed = cnt;
	sum -= Dinic::Dinic(s, t);
	cout << fixed << setprecision(1) << sum / 10.0;
	return 0;
}
/*
反正也不差那个 log，直接用 map
*/