不会用并查集的路过...
我的做法是:
首先用Floyd求出目前所有物品中,两两之间是否可换(即两者间是否连通),确定最短兑换路径.
并且同时记录下每两个物品之间兑换的最短路径.
最后,遍历该路径,通过不断求最小公倍数来统一最后的物品兑换比.
此外,将上述的兑换比更新到图中,以便后续计算.

举个例子说,
要询问A->C最后的兑换比,并且通过上述预处理后我们已经知道了最短的兑换路径是A->B->C,
而且:
A->B 兑换比为 i:j
B->C 兑换比为 m:n

那么沿着该路径,则有A->C最终的兑换比为:
i*Lcm(j,m)/j : n*Lcm(j,m)/m

并且最后不要忘记将比值约分至最简.