题目详情题解（0）讨论（0）提交记录（0）

AT_abc373_d.[ABC373D] Hidden Weights

普及-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个有 NN 个顶点、MM 条边的有向图。第 jj 条有向边从顶点 uju_j 指向顶点 vjv_j，权值为 wjw_j。

请找出一种方法，将 −1018-10^{18} 到 101810^{18} 之间的整数写在每个顶点上，使得满足以下条件：

  • 设顶点 ii 上写的数为 xix_i。对于所有边 j=1,2,…,Mj=1,2,\dots,M，都有 xvj−xuj=wjx_{v_j} - x_{u_j} = w_j。

保证对于给定的输入，至少存在一种满足条件的写法。

输入格式

输入以如下格式从标准输入读入。

NN MM
u1u_1 v1v_1 w1w_1
u2u_2 v2v_2 w2w_2
⋮\vdots
uMu_M vMv_M wMw_M

输出格式

请输出一行，用空格分隔的 x1,x2,…,xNx_1,x_2,\dots,x_N，其中 xix_i 表示写在顶点 ii 上的整数。若有多种答案，输出任意一种均可。

输入输出样例

  • 输入#1

    3 3
1 2 2
3 2 3
1 3 -1

    输出#1

    3 5 2

  • 输入#2

    4 2
2 1 5
3 4 -3

    输出#2

    5 0 6 3

  • 输入#3

    5 7
2 1 18169343
3 1 307110901
4 1 130955934
2 3 -288941558
2 5 96267410
5 3 -385208968
4 3 -176154967

    输出#3

    200401298 182231955 -106709603 69445364 278499365

说明/提示

限制条件

  • 2≤N≤2×1052 \leq N \leq 2 \times 10^5
  • 1≤M≤min⁡{2×105,N(N−1)/2}1 \leq M \leq \min\{2 \times 10^5, N(N-1)/2\}
  • 1≤uj,vj≤N1 \leq u_j, v_j \leq N
  • uj≠vju_j \neq v_j
  • 若 i≠ji \neq j，则 (ui,vi)≠(uj,vj)(u_i, v_i) \neq (u_j, v_j) 且 (ui,vi)≠(vj,uj)(u_i, v_i) \neq (v_j, u_j)
  • ∣wj∣≤109|w_j| \leq 10^9
  • 输入均为整数
  • 保证至少存在一种满足条件的写法

样例解释 1

例如取 x=(3,5,2)x=(3,5,2)，则 x2−x1=w1=2x_2-x_1=w_1=2，x2−x3=w2=3x_2-x_3=w_2=3，x3−x1=w3=−1x_3-x_1=w_3=-1，均满足条件。
也可以取 x=(−1,1,−2)x=(-1,1,-2)，同样是正确答案。

样例解释 2

例如取 x=(0,−5,4,1)x=(0,-5,4,1) 或 x=(5,0,4,1)x=(5,0,4,1)，都是正确答案。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页