【BZOJ-4690】Never Wait For Weights 带权并查集

4690: Never Wait for Weights

Time Limit: 15 Sec Memory Limit: 256 MB
Submit: 88 Solved: 41
[Submit][Status][Discuss]

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

HINT

Source

鸣谢Tangjz提供试题

Solution

典型的思博题了啊

随便写个带权并查集，delta[i]记录到集合的代表元素的差值，然后就可以了

Code

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

inline int read()

{

    int x=,f=; char ch=getchar();

    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}

    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}

    return x*f;

}

#define MAXN 100010

int N,M;

int fa[MAXN],delta[MAXN];

inline void Init() {for (int i=; i<=N; i++) fa[i]=i,delta[i]=;}

inline int F(int x) {if (x==fa[x]) return x; int Fa=F(fa[x]); delta[x]+=delta[fa[x]]; return fa[x]=Fa;}

inline void Merge(int x,int y,int d)

{

    int Fx=F(x),Fy=F(y);

    if (Fx==Fy) return;

    int Fa=fa[x];

    fa[Fa]=fa[y]; delta[Fa]=delta[y]+d-delta[x];

}

int main()

{

    while (scanf("%d%d",&N,&M))

        {

            if (!N && !M) break;

            Init();

            while (M--)

                {

                    char opt[]; scanf("%s",opt); int u=read(),v=read(),d;

                    if (opt[]=='!') d=read(),Merge(u,v,d);

                    if (opt[]=='?')

                        if (F(u)!=F(v)) puts("UNKNOWN"); else printf("%d\n",delta[u]-delta[v]);

                }

        }

    return ;

}

这思博题我还能WA？

然而因为打的太快了...手误了一个地方....然后真的WA了....

暗言术：WA！

秒客网