首页 > 代码库 > BZOJ 4690 Never Wait for Weights

BZOJ 4690 Never Wait for Weights

带权并查集23333333

注意dis[x]+=dis[fath[x]。

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define maxn 100500using namespace std;int n,m,x,y,z,fath[maxn],dis[maxn];char s[5];int getfather(int x){    if (fath[x]==x) return x;    int ret=getfather(fath[x]);    dis[x]+=dis[fath[x]];fath[x]=ret;    return ret;}void unionn(){    int f1=getfather(x),f2=getfather(y);    if (f1==f2) return;    int ret=z+dis[x]-dis[y];    fath[f2]=f1;dis[f2]=ret;    return;}void ask(){    int f1=getfather(x),f2=getfather(y);    if (f1!=f2) printf("UNKNOWN\n");    else printf("%d\n",dis[y]-dis[x]);}int main(){    for (;;)    {        scanf("%d%d",&n,&m);        if ((n==0) || (m==0)) break;        for (int i=1;i<=n;i++)        {            fath[i]=i;            dis[i]=0;        }        for (int i=1;i<=m;i++)        {            scanf("%s",s);            if (s[0]==!)             {                scanf("%d%d%d",&x,&y,&z);                unionn();            }            else            {                scanf("%d%d",&x,&y);                ask();            }        }    }    return 0;}

 

BZOJ 4690 Never Wait for Weights