Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom1年前

11/4
22:08
并查集

[bzoj 4690] Never Wait for Weights

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

在实验室中,Nathan Wada作为助手的职责是测定两个样品的重量差异。当样品的差异很小时,使用天平能比使用弹簧秤得到更精确的结果,所以他只使用天平来测得一些样品的重量差。他偶尔会被询问一些样品的重量差,而他能否回答这些问题取决于在回答相应问题时他已经得到的测量结果。由于他所在处理的测量数据是巨大的,所以他希望你能写个程序帮他处理数据和回答问题。

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

输入包含多组测试数据。每组数据第一行包含两个整数 N 和 M ,其中 N 表示样品的数量,样品从 1 到 N 标号,满足 2≤N≤100000 。接下来 M 行,每行包括一个测量结果或者询问,按时间顺序给出,满足 1≤M≤100000 。一个测量结果被格式化为 ! a b w ,表示第 a 个样品比第 b 个样品轻 w 个单位重量满足 a≠b,0≤w≤1000000 ,且任意的测试结果互不矛盾。一个询问被格式化为 ? a b ,表示询问第 a 个样品比第 b 个样品轻多少个单位重量,满足 a≠b 。输入以两个零作为结束。

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

对于每个询问输出一行,如果能回答问题,则输出问题的答案,你可以认为答案的绝对值不超过 1000000
否则输出 UNKNOWN ,表示不能回答问题。

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

  1. 2 2
  2. ! 1 2 1
  3. ? 1 2
  4. 2 2
  5. ! 1 2 1
  6. ? 2 1
  7. 4 7
  8. ! 1 2 100
  9. ? 2 3
  10. ! 2 3 100
  11. ? 2 3
  12. ? 1 3
  13. ! 4 3 150
  14. ? 4 1
  15. 0 0 

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

1
-1
UNKNOWN
100
200
-50

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

用并查集来维护差值,路径压缩的时候顺便把这些差值也压缩一下

 

[bzoj 4690] Never Wait for Weights