RQNOJ36 数石子并查集简单应用

题目描述

佳佳是个贪玩的孩子。一天，他正在跟凡凡玩“数石子”的游戏。佳佳在地上摆了Ｎ堆石子，其中第Ｉ堆石子有Ａi个石头。佳佳每次都会问凡凡：“凡凡，请问从第Ｉ堆到第Ｊ堆，总共有多少个石子？”聪明的凡凡每次都能快速而准确地回答对。凡凡老是被问问题，心里有些不服，就对佳佳说：“佳佳，你还记得你问了什么问题，我回答了什么答案吗？”佳佳说当然记得。于是凡凡说：“好，我把石子拿走，再问你一些相似的问题，你能答得出来吗？”佳佳张圆了嘴巴，望着凡凡，一脸疑问和惊讶的表情。你现在知道了游戏规则和过程，但没看见原来的石子。请你写一个程序来帮助佳佳。

数据范围

10%的数据满足1<=n<=10,0<=m,k<=10

30%的数据满足1<=n<=500,0<=m,k<=500

100%的数据满足1<=n<=5000,0<=m,k<=10000

输入格式

输入文件的第一行有３个数Ｎ(1<=n<=5000)，Ｍ，Ｋ(0<=m,k<=10000)，表示Ｎ堆石子，佳佳问了Ｍ个问题，凡凡要问Ｋ个问题。接下来Ｍ行每行３个整数Ｌ，Ｒ（1<=l<=r<=n），Ｘ(-108<=X<=108)，表示佳佳问从Ｌ堆到Ｒ堆的石子共有多少个，而凡凡回答Ｘ个。接下来Ｋ行每行２个整数Ａ，Ｂ(1<=a<=b<=n)，每行表示凡凡问从Ａ到Ｂ这些堆里的石子有多少个。

输出格式

输出文件需要对于凡凡提出每一个提问，你若可以回答，则输出答案，若无法回答，输出UNKNOWN。

样例输入

样例输出

一开始想着把已知的所有线段的两端的数字看成是节点，石子数看成是线段的权值，每次都把大的这一端挂到小的这一端上。

但是这样会出现一个问题，已知1-5,2-5,我们可以知道1-1的值，但是仅仅通过归并之后的树并没有办法直接算出来，在这里可以采取一些处理方式。

把所有的区间变成是左开右闭的区间，这样子的话1-5,2-5就变成了0-5,1-5，合并之后变成了0为根节点的树有两个儿子1和5，这样我们就可以查询1-1和2-5，通过查询同样的左开右闭区间0-1,1-5即可

至于归并的过程就是简单的带权值并查集的归并，无脑写即可

#include <cstdio>
#include <cstring>

using namespace std;

const int maxn = 50000 + 5;
int fa[maxn],dist[maxn],N,M,K;

int f(int a) {
    if(fa[a] == a) return a;
    int root = f(fa[a]);
    dist[a] = dist[a] + dist[fa[a]];
    fa[a] = root;
    return root;
}

void uni(int a,int b,int d) {
    a = a - 1;
    int ya = f(a),yb = f(b);
    if(ya == yb) return;
    fa[yb] = a;
    dist[yb] = d - dist[b];
}

int main() {
    scanf("%d%d%d",&N,&M,&K);
    for(int i = 1;i <= N;i++) {
    fa[i] = i;
    }
    for(int i = 1;i <= M;i++) {
	int a,b,d; scanf("%d%d%d",&a,&b,&d);
	uni(a,b,d);
    }
    for(int i = 1;i <= K;i++) {
	   int a,b; scanf("%d%d",&a,&b);
	   a--;
	   int ya = f(a),yb = f(b);
	   if(ya != yb) puts("UNKNOWN");
	   else {
	       printf("%d
",dist[b] - dist[a]);
	   }
    }
    return 0;
}

RQNOJ36 数石子 并查集 简单应用

RQNOJ36 数石子并查集简单应用