Hiho-1515丨带权并查集

#include
#include
#include
#include
using namespace std;
const int N = 100005;
int pre[N],v[N];
int n,m,s,q;
/* https://hihocoder.com/problemset/problem/1515
 * 题意：告知一些列人的分数关系，询问一些列人的分数关系
 * 思路：带权并查集，今天学的时候听的不算很透彻，真正做题的时候还是卡了一下
 * 用pre[i]来代表i的前驱，v[i]代表i比pre[i]要高v[i]分；
 * 具体细节见下面的注释。
 */
int findpre(int x)//查找前驱
{
 if(pre[x]==x)return x;
 else {
  int t=pre[x];//记录当前的前驱
  pre[x]=findpre(pre[x]);//当前前驱赋成根
  v[x]+=v[t];//v[x],原本表示，x之于t的分数，现在路径压缩，所以加上v[t]
  return pre[x];
 }
}

int main(){
 scanf("%d%d%d",&n,&m,&q);
 for(int i=1;i<=n;i++)
 {
  pre[i]=i;
  v[i]=0;//i比pre[i]要高v[i]分；
 }

 int x,y,val,fx,fy;
 while(m--){
  //这里对应原并查集合并的操作
  scanf("%d%d%d",&x,&y,&val);
  fx=findpre(x);
  fy=findpre(y);
  if(fx!=fy){
pre[fx]=fy;
v[fx]+=v[y]-v[x]+val;
/* 我们假设下gx表示x的真实分数，同理可得
 * gx=gfx+v[x] x的分数比fy高v[x]
 * gy=gfy+v[y]
 *
 * gx-gy=val x比y高val
 * gfx-gfy=v[fx]
 * 做差即可得到上式
 */
  }
 }
 while(q--){
  scanf("%d%d",&x,&y);
  fx=findpre(x);
  fy=findpre(y);
  if(fx==fy){
//如果有公共的根，说明可以比较，没有就不可比呀
printf("%d\n",v[x]-v[y]);
  } else puts("-1");
 }
 return 0;
}
/*
*/