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

2 2

! 1 2 1

? 1 2

2 2

! 1 2 1

? 2 1

4 7

! 1 2 100

? 2 3

! 2 3 100

? 2 3

? 1 3

! 4 3 150

? 4 1

0 0

Sample Output

1

-1

UNKNOWN

100

200

-50

Solution

带权并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<queue>
#include<vector>
#include<algorithm>
#include<cmath>
#include<stack>
#include<map>
using namespace std;
#define R register
#define ll long long
#define fo(i,a,b) for(R int (i)=(a);(i)<=(b);++(i))
#define dbg(x) cout<<#x<<"="<<x<<'\n'
#define mmt(x,y) memset(x,y,sizeof(x))
int n,m,fa[200000],v[200000];
int find(int x)
{
if(x==fa[x])return x;
R int rt=find(fa[x]);
v[x]+=v[fa[x]];
fa[x]=rt;
return rt;
}
int main()
{
while(scanf("%d%d",&n,&m),n&&m)
{
mmt(v,0);
fo(i,1,n)fa[i]=i;
while(m--)
{
R char odd[2];int x,y,w;
scanf("%s",odd);
if(odd[0]=='!')
{
scanf("%d%d%d",&x,&y,&w);
R int f1=find(x),f2=find(y);
fa[f2]=f1;
v[f2]=v[x]-v[y]-w;
}
else
{
scanf("%d%d",&x,&y);
R int f1=find(x),f2=find(y);
if(f1!=f2)puts("UNKNOWN");
else printf("%d\n",v[x]-v[y]);
}
}
}
return 0;
}

显示 Gitment 评论