HYSBZ 4690 Never Wait for Weights（变种并查集）

ゝ一纸荒年。 2022-06-04 03:57 87阅读 0赞

在实验室中，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

题解：

并查集操作，就是路径压缩的时候也要更新一遍信息，很有意思的一题

代码：

#include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    #include<queue>
    #include<stack>
    #include<math.h>
    #include<vector>
    #include<map>
    #include<set>
    #include<stdlib.h>
    #include<cmath>
    #include<string>
    #include<algorithm>
    #include<iostream>
    #include<stdio.h>
    using namespace std;
    #define ll long long
    int pre[100005];
    map<pair<int,int>,int>M;
    int ans;
    struct inf
    {
        int index;
        int v;
    };
    inf find(int x)
    {
        if(x!=pre[x])
        {
            inf t=find(pre[x]);
            pair<int,int>t1;
            t1.first=x;
            t1.second=pre[x];
            t.v+=M[t1];
            t1.second=t.index;
            M[t1]=t.v;
            pre[x]=t.index;
            return t;
    
        }
        else
        {
            inf t;
            t.index=x;
            t.v=0;
            return t;
        }
    }
    int main()
    {
        int i,j,n,m,a,b,w,u;
        char qu[10];
        while(scanf("%d%d",&n,&m)!=EOF)
        {
            if(n==0&&m==0)
                break;
            for(i=1;i<=n;i++)
            {
                pre[i]=i;
            }
            M.clear();
            for(i=1;i<=m;i++)
            {
                scanf("%s%d%d",qu,&a,&b);
                if(qu[0]=='!')
                {
                    scanf("%d",&w);
                    inf d1=find(a);
                    inf d2=find(b);
                    if(d1.index!=d2.index)
                    {
                        pair<int,int>t1;
                        t1.first=d1.index;
                        t1.second=b;
                        M[t1]=w-d1.v;
                        pre[d1.index]=b;
                    }
                }
                else
                {
                    inf d1=find(a);
                    inf d2=find(b);
                    if(d1.index!=d2.index)
                        printf("UNKNOWN\n");
                    else
                    {
                        int u=d1.index;
                        pair<int,int>t1;
                        t1.first=a;
                        t1.second=u;
                        pair<int,int>t2;
                        t2.first=b;
                        t2.second=u;
                        printf("%d\n",M[t1]-M[t2]);
                    }
                }
            }
        }
        return 0;
    }