当前位置: 代码迷 >> 综合 >> hiho#1515 分数调查(带权并查集的经典应用)
  详细解决方案

hiho#1515 分数调查(带权并查集的经典应用)

热度:16   发布时间:2023-11-22 00:40:28.0

题目链接

http://hihocoder.com/problemset/problem/1515

题目

小Hi的学校总共有N名学生,编号1-N。学校刚刚进行了一场全校的古诗文水平测验。

学校没有公布测验的成绩,所以小Hi只能得到一些小道消息,例如X号同学的分数比Y号同学的分数高S分。

小Hi想知道利用这些消息,能不能判断出某两位同学之间的分数高低?

Input
第一行包含三个整数N, M和Q。N表示学生总数,M表示小Hi知道消息的总数,Q表示小Hi想询问的数量。

以下M行每行三个整数,X, Y和S。表示X号同学的分数比Y号同学的分数高S分。

以下Q行每行两个整数,X和Y。表示小Hi想知道X号同学的分数比Y号同学的分数高几分。

对于50%的数据,1 <= N, M, Q <= 1000

对于100%的数据,1 <= N, M, Q<= 100000 1 <= X, Y <= N -1000 <= S <= 1000

数据保证没有矛盾。

Output
对于每个询问,如果不能判断出X比Y高几分输出-1。否则输出X比Y高的分数。

Sample Input
10 5 3
1 2 10
2 3 10
4 5 -10
5 6 -10
2 5 10
1 10
1 5
3 5
Sample Output
-1
20
0

分析

并查集的本质是森林,每棵树代表一个集合,树根是集合的代表元。给树边一个权值,sum[u]表示结点u到u的父结点的距离,与题目联系就是:
sum[u]等于u的父结点比u高的分数。
对于每个x y v,x比y高v分,连一条边,x是y的父结点且权值为v。并通过并查集的压缩路径操作将x的父结点调整为根。
要能够判断x,y分数差。要求x和y在一棵树上,根据x到树根的距离与y到树根的距离求结果。否则,不能判断。

AC代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+100;
int par[maxn],N,M;
int sum[maxn];//sum[i]表示i到i的父结点的距离,即i的父结点比i高的分数
void init()
{for(int i=0;i<=N;i++) par[i]=i;memset(sum,0,sizeof(sum));
}
int find(int x)
{if(par[x]!=x){int tmp=par[x];par[x]=find(par[x]);sum[x]+=sum[tmp];}return par[x];
}
void unit(int x,int y,int v)
{int fx=find(x),fy=find(y);if(fx==fy)//在一棵树上{return ;}else{par[fx]=fy;sum[fx]=sum[y]-sum[x]-v;}return ;
}
bool same(int x,int y)
{return find(x)==find(y);
}
int main()
{int q;while(~scanf("%d%d%d",&N,&M,&q)){init();while(M--){int x,y,v;scanf("%d%d%d",&x,&y,&v);unit(x,y,v);}while(q--){int x,y;scanf("%d%d",&x,&y);printf("%d\n",same(x,y)?sum[y]-sum[x]:-1);}}return 0;
}