首页 > 代码库 > bzoj4690: Never Wait for Weights 并查集

bzoj4690: Never Wait for Weights 并查集

裸带权并查集

#include<cstdio>#define N 100005int m,i,j,s,t,u,d[N],p[N];char k;int find(int i){	if(p[i]^i&&find(p[i]))		d[i]+=d[p[i]];	return p[i]=p[p[i]];}int main(){	while(scanf("%d%d",&s,&m)&&s){		for(;s;--s)			d[p[s]=s]=0;		while(m--){			scanf(" %c%d%d",&k,&s,&t);			i=find(s),j=find(t);			if(k==‘!‘){				scanf("%d",&u);				p[i]=j;				d[i]=d[t]+u-d[s];			}else if(i^j)				puts("UNKNOWN");			else				printf("%d\n",d[s]-d[t]);		}	}}

  

bzoj4690: Never Wait for Weights 并查集