自动搬运

查看原文

来自洛谷，原作者为

	Ephemeroptera AFOed

搬运于2025-08-24 22:03:05，当前版本为作者最后更新于2022-03-23 10:19:07，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Solution:

这题楼上已经讲得很清楚了，就是考虑将人看成边去连接两个点，将点分配给边获得相应的权值。有解当且仅当连出来的图是一个基环树森林。

而基环树森林是方便将点分配给边的。因为对于树的部分，方案已经确定。对于环的部分，分配分成顺时针和逆时针两种情况。而在这一道题中，因为一条边肯定连接的是左边和右边，得到的是一个偶环，也就是说，顺时针分配得到的权值和逆时针分配得到的权值是相反数。

因为要求得两边的权值差在 $k$ 内是否有解，这个问题结合上这个基环树森林可以用背包解决。可以先假定都取顺时针顺序，然后用逆时针顺序减去顺时针顺序作为权值去做，但复杂度为 $O(\frac {n^2a}{w})$ 。另外一篇题解好像是用这个不正确的复杂度通过的。

注意到做的是背包，并且总权值是 $na$ 的，可以得知不同的个数在 $\sqrt{na}$ 内，做多重背包就好了。单调队列没法 bitset 优化，所以使用二进制分组。但是需要注意的是，二进制分组在这里的复杂度是 $O(\frac{na\sqrt{na}}{w})$ 的而非楼上题解所写的是 $O(\frac{na\sqrt{na}log(\sqrt{na})}{w})$。

因为这里的 $log$ 并不能简单的写成 $log(na)$，复杂度应该写成 $\frac{na\sum_i^{cnt}log(b_i)}{w}$ ，其中 $cnt$ 是不同权值的个数，$b_i$ 是第 $i$ 个权值的个数。其中满足 $\sum_i^{cnt}b_i*val_i \le na$。这个东西实际上是可以被证明是常数。

code:

#include <bits/stdc++.h>



using namespace std;
const int N = 2e5 + 10;
int n, k, m, bas;
int c[N];
int first[N], nex[N << 1], v[N << 1], w[N << 1], num = 1;
int vis[N], cir[N], sav[N], stu[N], top = 0; 
int val[N], len[N], cnt = 0;
struct node {
	int val, cnt;
}a[N];
int edg = 0, ver = 0;
bitset<N * 20> dp;
inline void add(int x, int y, int z) {
	v[++num] = y;
	w[num] = z;
	nex[num] = first[x];
	first[x] = num;
}
inline void Find_cir(int u, int fa) {
	if (vis[u]) {
		for (int i = top; i >= 1; i--) {
			cir[stu[i]] = true;
			sav[++len[cnt]] = stu[i];
			if (stu[i] == u) break;
		}
		return ;
	}
	stu[++top] = u;
	ver++;
	vis[u] = true;
	for (int i = first[u]; i != -1; i = nex[i]) {
		int to = v[i];
		if ((i ^ fa) != 1 && !cir[to]) {
			edg++;
			Find_cir(to, i);	
		}
	}
	top--;
}
inline void DFS(int u, int fa) {
	for (int i = first[u]; i != -1; i = nex[i]) {
		int to = v[i];
		if (!cir[to] && fa != to) {
			m += (to > n ? -w[i] : w[i]);
			DFS(to, u);
		}
	}
}
inline void dfs(int Rot, int u, int fa) {
	for (int i = first[u]; i != -1; i = nex[i]) {
		int to = v[i];
		if ((fa ^ i) != 1 && cir[to]) {
			val[cnt] += (u > n ? -w[i] : w[i]);
			if (Rot != to) dfs(Rot, to, i);
		}
	}
}
inline void sol() {
	for (int i = 1; i <= len[cnt]; i++) DFS(sav[i], 0);
	for (int i = first[sav[1]]; i != -1; i = nex[i]) {
		int to = v[i];
		if (cir[to]) {
			val[cnt] += (sav[1] > n ? -w[i] * 2 : w[i] * 2);
			dfs(sav[1], to, 0);
			break;
		} 
	}
	m += -val[cnt];
	val[cnt] = 2 * val[cnt];
}
int main() {
	memset(first, -1, sizeof first);
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> k;
	for (int i = 1; i <= n * 2; i++) {
		int x, y;
		cin >> x >> y >> c[i];
		add(x, y + n, c[i]);
		add(y + n, x, c[i]);
	}
	for (int i = 1; i <= n * 2; i++) {
		if (!vis[i])  {
			ver = 0, edg = 0;
			++cnt;
			Find_cir(i, 0);
			if (ver != edg) {
				cout << "NO\n";
				return 0;
			}
			sol();
		}
	}
	sort(val + 1, val + cnt + 1);
	int tem = cnt; cnt = 0; 
	val[0] = -2e9;
	for (int i = 1; i <= tem; i++) {
		if (val[i] != val[i - 1]) {
			a[++cnt].val = val[i];
			a[cnt].cnt = 1;
		} else a[cnt].cnt++;
	}
	bas = n * 20;
	dp[bas] = 1;
	for (int i = 1; i <= cnt; i++) {
		for (int j = 1; a[i].cnt; j = min(j * 2, a[i].cnt -= j)) {
			if (a[i].val < 0) dp = (dp | (dp >> (-a[i].val * j)));
			else dp = (dp | (dp << (a[i].val * j)));
		}
	} 
	bool ans = 0;
	for (int i = -k; i <= k; i++) ans |= dp[i + bas - m];
	if (ans) cout << "YES\n";
	else cout << "NO\n";
	return 0;
}