luogu#P11170. 「CMOI R1」图上交互题 / Constructive Minimum Xor Path
「CMOI R1」图上交互题 / Constructive Minimum Xor Path
题目背景
2024 年 1 月 13 日 15:59:31,随着最后一发交互 J 题的提交出现了 Wrong Answer,小 G 的 EC-Final 比赛结束了,也意味着在 ICPC 生涯中第一次打铁。
痛定思痛,小 G 决定批量生产交互题给自己做。如何批量生产交互题?只要在一个数据结构中有若干个未知量 ,每次询问给定向量 ,交互库会返回关于 的函数 ,这样就能批量生产交互题了!
那为什么这题并不是交互题呢。
题目描述
给定一个 个点, 条边的无向图。第 条边 有一个未知边权 。
对于任何一条路径,定义其代价如下:设路径为 ,其中要求 是无向图中的边,设其为第 条边。那么路径的代价即为 。其中 表示异或。(该路径可以经过重复点和重复边,即 和 可以包含重复的数)
定义 为从 到 的所有路径中代价的最小值。特别地,当 时,。
给定 ,再对于每条边 给定 ,你需要求出是否存在一组合法的 ,如果有解,你还需要构造一组解。
输入格式
第一行两个正整数 。
第 行每行两个正整数 和一个非负整数 。
请注意:本题并不保证图连通;可能会存在重边和自环。
输出格式
如果不存在解,则仅输出 No
。
否则,在第一行输出 Yes
,在第二行输出 个非负整数 表示一组合法的解。
答案可能有很多组,此时输出任意一组解即可。你需要保证 输出的 。
3 3
1 2 2
2 3 3
3 1 1
Yes
2 3 114514
1 1
1 1 1
No
提示
样例解释
答案输出的图如下:
考虑 :
-
考虑路径 ,路径的代价为 。
-
考虑路径 $1\rightarrow 2\rightarrow 3\rightarrow 1\rightarrow 2$,路径的代价为 。
此外还存在其他路径,但可以证明不存在代价比 更小的路径,故 。
数据范围
本题采用捆绑测试。
特殊性质 | 分数 | |
---|---|---|
保证有解 | ||
对于 的数据,,,。