洛谷 AT_abc373_d [ABC373D] Hidden Weights 题解

题目大意

有一个有 $N$ 个点 $M$ 条边的有向图，第 $i$ 条边由 $u_i$ 到 $v_i$，权值为 $w_i$。

需要你对图中的每个节点填上一个介于 $-10^{18}$ 到 $10^{18}$ 之间的整数，使得满足以下条件：

• 如果 $x_i$ 为第 $i$ 个点的值，则对于任意的一个 $j\in [1,M]$，满足 $x_{v_j}-x_{u_j}=w_j$。

保证题目有解，该图不一定连通。

题目思路

不妨可以先假定该图连通，那么可以以任意一个点为起点出发，设该点数值为 $0$，再进行 dfs 求值。由于 $N\le 2\times 10^5,|w_i|\le 10^9$，所以每个节点的值都属于区间 $[-2\times 10^{14},2\times 10^{14}]$，并不会爆 long long。

但我们现在要计算的图不一定连通，但可以将其分为多个连通子图进行求值，由此，即可达到对全图求值的目的。

Code

#include <iostream>
#define int long long
using namespace std;
int n, m, u, v, w[200001], ans[200001];
int nxt[200001], head[200001], to[200001], tot;
int nxt1[200001], head1[200001], to1[200001];
bool flag[200001];
void dfs(int u, int sum) {//搜索
	if (flag[u]) return;//若已经搜索过则跳过
	flag[u] = true;//标记为已搜索
	ans[u] = sum;//更新值
	for (int i = head[u]; i; i = nxt[i]) dfs(to[i], sum + w[i]);//枚举以该点出发的边
	for (int i = head1[u]; i; i = nxt1[i]) dfs(to1[i], sum - w[i]);//枚举以该点为终点的边
}
void add() {//链式前向星
	to[tot] = v;
	nxt[tot] = head[u];
	head[u] = tot;
	to1[tot] = u;//反向存储一遍
	nxt1[tot] = head1[v];
	head1[v] = tot;
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(), cout.tie();
	cin >> n >> m;
	for (tot = 1; tot <= m; ++tot) {
		cin >> u >> v >> w[tot];
		add();
	}
	for (int i = 1; i <= n; ++i) if (!flag[i] && head[i]) dfs(i, 0);//如果有连边且为访问过则进行 dfs
	for (int i = 1; i <= n; ++i) cout << ans[i] << " ";
	return 0;
}

祝各位 AK CSP