CF1715D 题解

前言

题目传送门！

更好的阅读体验？

感觉挺不错的一道图论转化题。（其实也和图论关系不大。）

思路

对于每个条件 /(a_u /mid a_v = x/)，二进制拆掉 /(x/)。如果 /(x/) 的二进制位 /(j/) 是 /(1/)，说明 /(a_u/) 和 /(a_v/) 中，当前位也肯定有至少一个为 /(1/)。标记一下 /(f_{u, j} = f_{v, j} = 1/)。

由于字典序最小，所以我们尽量只让 /(a_{/max(u, v)}/) 的对应二进制位为 /(1/)，这样可以使得 /(a_{/min(u, v)}/) 小一些。

由于要表示出点与点之间的关系，我们尝试建图。对每一个条件建图：连一条 /(u/) 与 /(v/) 间，边权为 /(x/) 的双向边。

然后，枚举每一位二进制位 /(j/)，以及每一个点。对于每一个点，看与之相连的其他所有点（仍然是记为 /(u/), /(v/), /(x/)）。

我们现在是看 /(a_u/) 的第 /(j/) 位（指的是二进制下。之后同理），要不要变成 /(1/)。

如果 /(x/) 的第 /(j/) 位是 /(0/)，就跳过。否则，看 /(u/) 与 /(v/) 的大小关系。

• 如果 /(u < v/)，那么如果 /(f_v/) 的第 /(j/) 位没有被标记过，/(a_u/) 的第 /(j/) 位才必须为 /(1/)。否则应该让 /(a_v/) 为 /(1/)，这样 /(u/) 就能小一些了。
• 如果 /(u > v/)，那么看当前 /(a_v/) 的结果。如果 /(a_v/) 的第 /(j/) 位为 /(0/)，那 /(a_u/) 的第 /(j/) 位才必须为 /(1/)。

你可能会问，/(u = v/) 怎么办？显然 /(a_u /mid a_u = x/)，直接表明了 /(a_u = x/)。因此在第一步时，就能特判掉 /(u = v/) 的情况，避免自环。

完整代码

#include <iostream>
#include <cstdio>
#define space putchar(' ')
#define endl putchar('/n')
using namespace std;
int read()
{
	char op = getchar(); int x = 0, f = 1;
	while (op < 48 || op > 57) {if (op == '-') f = -1; op = getchar();}
	while (48 <= op && op <= 57) x = (x << 1) + (x << 3) + (op ^ 48), op = getchar();
	return x * f;
}
void write(LL x)
{
	if (x < 0) putchar('-'), x = -x;
	if (x > 9) write(x / 10);
	putchar(x % 10 + 48);
}
const int N = 1e5 + 5, M = 2e5 + 5;
struct Edge
{
	int now, nxt, w;
}e[M << 1]; //这里空间要开足！赛时调了好久。 
int head[N], cur;
void add(int u, int v, int w)
{
	e[++cur].now = v;
	e[cur].nxt = head[u];
	e[cur].w = w;
	head[u] = cur;
}
bool bit(int x, int j) {return x & (1 << (j - 1));} //x 的第 j 位 
bool flag[N][35]; //flag[i][j]表示a[i]的第j位是否有可能为1
int a[N];
bool calc(int u, int j)
{
	for (int i = head[u]; i; i = e[i].nxt)
	{
		int v = e[i].now, x = e[i].w;
		if (!bit(x, j)) continue;
		if (u < v) {if (flag[v][j]) return true;}
		else {if (!bit(a[v], j)) return true;}
	}
	return false;
}
int main()
{
	int n = read(), m = read();
	for (int i = 1; i <= m; i++)
	{
		int u = read(), v = read(), x = read();
		for (int j = 1; j <= 30; j++)
			if (!bit(x, j))
				flag[u][j] = flag[v][j] = true;
		if (u == v) {a[u] = x; continue;} //特判，避免加边时造成自环 
		add(u, v, x), add(v, u, x);
	}
	for (int j = 1; j <= 30; j++)
		for (int i = 1; i <= n; i++)
			if (calc(i, j))
				a[i] |= (1 << (j-1));
	for (int i = 1; i <= n; i++) write(a[i]), space;
	return 0;
}

希望能帮助到大家！

首发：2022-08-25 14:57:13