BZOJ4690: Never Wait for Weights

【傳送門：BZOJ4690】

簡要題意：

　　有n個物品，m個操作，兩種操作：

　　! a b w表示第a個物品比第b個物品重量輕w

　　? a b求出a比b輕多少，如果無法求出答案則輸出UNKNOWN

題解：

　　帶權并查集，對于!操作，預設編号小的在前面，如果要交換則w=-w

　　然後直接做就好了

參考代碼：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
int fa[110000],v[110000];
int findfa(int x)
{
    if(fa[x]==x) return x;
    int f=fa[x];
    fa[x]=findfa(fa[x]);
    v[x]+=v[f];
    return fa[x];
}
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(n==0&&m==0) break;
        memset(v,0,sizeof(v));
        for(int i=0;i<=n;i++) fa[i]=i;
        bool bk=true;char st[3];
        for(int i=1;i<=m;i++)
        {
            int x,y,k;
            scanf("%s%d%d",st+1,&x,&y);
            if(st[1]=='!')
            {
                scanf("%d",&k);
                if(x>y) k=-k,swap(x,y);
                int fx=findfa(x),fy=findfa(y);
                if(fx!=fy)
                {
                    fa[fy]=fx;
                    v[fy]=k-v[y]+v[x];
                }
            }
            else
            {
                int fx=findfa(x),fy=findfa(y);
                if(fx!=fy) printf("UNKNOWN\n");
                else printf("%d\n",v[y]-v[x]);
            }
        }
    }   
    return 0;
}      

轉載于:https://www.cnblogs.com/Never-mind/p/8858623.html