【[Offer收割]编程练习赛15-B分数调查】

本文主要是介绍【[Offer收割]编程练习赛15-B分数调查】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【链接】https://hihocoder.com/contest/offers15/problems
【题目描述】
题目2 : 分数调查
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
小Hi的学校总共有N名学生，编号1-N。学校刚刚进行了一场全校的古诗文水平测验。

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

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

输入
第一行包含三个整数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

数据保证没有矛盾。

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

样例输入
10 5 3
1 2 10
2 3 10
4 5 -10
5 6 -10
2 5 10
1 10
1 5
3 5
样例输出
-1
20
0
【思路】：脑残+手残，其实最后都快写出来了，就差那么一点点，好吧，其实已经好久没刷题了，脑袋思维+手速熟练度明显下降！明显的带权并查集操作，代码如下：

/***********************
[Offer收割]编程练习赛15     【B分数调查】
Author：herongwei
Time:2017/4/23 14:00
language：C++
http://blog.csdn.net/u013050857
***********************/
#pragma comment(linker,"/STACK:102400000,102400000")
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <set>
#include <stack>
#include <math.h>
#include <map>
#include <queue>
#include <deque>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn = 1e5+10;
const LL MOD = 999999997;
const int inf= 0x3f3f3f3f;
int dir4[4][2]= {{1,0},{0,1},{-1,0},{0,-1}};
int dir8[8][2]= {{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};/*Super waigua */
#define INLINE __attribute__((optimize("O3"))) inline
INLINE char NC(void)
{static char buf[100000], *p1 = buf, *p2 = buf;if (p1 == p2){p2 = (p1 = buf) + fread(buf, 1, 100000, stdin);if (p1 == p2) return EOF;}return *p1++;
}INLINE void read(int &x)
{static char c;c = NC();int b = 1;for (x = 0; !(c >= '0' && c <= '9'); c = NC()) if(c == '-') b = -b;for (; c >= '0' && c <= '9'; x = x * 10 + c - '0', c = NC());x *= b;
}int fa[maxn],fen[maxn],vis[maxn];void init()
{for(int i=1; i<=maxn; ++i)fa[i]=i, fen[i]=0;
}/*find the father!!!!!*/
int find(int x)
{if(x==fa[x]) return x;else{int root = find( fa[x] );fen[x] += fen[fa[x]];return fa[x] = root;}
}/*Union!!!!!!!*/
int Union(int x,int y,int s)
{int fx=find(x);int fy=find(y);if(fx!=fy){fen[fy]=fen[x]+s-fen[y];fa[fy]=fx;}
}int main()
{//freopen("in.txt","r",stdin);int n,m,l;while(~scanf("%d %d %d",&n,&m,&l)){init();int x,y,s;for(int i=1; i<=m; ++i){read(x);read(y);read(s);Union(x,y,s);}for(int i=1; i<=l; ++i){read(x);read(y);if(find(x)!=find(y))puts("-1");else  printf("%d\n",fen[y]-fen[x]);}}return 0;
}