链接:hdu3038

• TT and FF are … friends. Uh… very very good friends -____-b
• FF is a bad boy, he is always wooing TT to play the following game with him. This is a very humdrum game. To
• begin with, TT should write down a sequence of integers-_-!!(bored).
• Then, FF can choose a continuous subsequence from it(for example the subsequence from the third to the fifth
• integer inclusively). After that, FF will ask TT what the sum of the subsequence he chose is. The next, TT
• will answer FF’s question. Then, FF can redo this process. In the end, FF must work out the entire sequence
• of integers.
• BoringBoringa very very boring game!!! TT doesn’t want to play with FF at all. To punish FF, she often
• tells FF the wrong answers on purpose.
• The bad boy is not a fool man. FF detects some answers are incompatible. Of course, these contradictions make
• it difficult to calculate the sequence.
• However, TT is a nice and lovely girl. She doesn’t have the heart to be hard on FF. To save time, she
• guarantees that the answers are all right if there is no logical mistakes indeed.
• What’s more, if FF finds an answer to be wrong, he will ignore it when judging next answers.
• But there will be so many questions that poor FF can’t make sure whether the current answer is right or wrong
• in a moment. So he decides to write a program to help him with this matter. The program will receive a series
• of questions from FF together with the answers FF has received from TT. The aim of this program is to find
• how many answers are wrong. Only by ignoring the wrong answers can FF work out the entire sequence of
• integers. Poor FF has no time to do this job. And now he is asking for your help~(Why asking trouble for
• himself~~Bad boy)
  

  Input

• Line 1: Two integers, N and M (1 <= N <= 200000, 1 <= M <= 40000). Means TT wrote N integers and FF asked her
• M questions.
• Line 2..M+1: Line i+1 contains three integer: Ai, Bi and Si. Means TT answered FF that the sum from Ai to Bi
• is Si. It’s guaranteed that 0 < Ai <= Bi <= N.
• You can assume that any sum of subsequence is fit in 32-bit integer.
  

  Output

• A single line with a integer denotes how many answers are wrong.
  

  Sample Input

  10 5
  1 10 100
  7 10 28
  1 3 32
  4 6 41
  6 6 1

  Sample Output

  1

  题解

• 带权并查集问题，一样的找向量偏移量 然后这题卡多组。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,x,y) for(register int i=x;i<=y;++i)
#define repd(i,x,y) for(regsiter int i=x;i>=y;--i)
#define ll long long
using namespace std;
const int N=1e6+7;
int f[N],rl[N],n,m,t,a,b,ans;

int (int x){
    if(f[x]==x)return x;
    int t=find(f[x]);
    rl[x]+=rl[f[x]];
    return f[x]=t;
}

inline void un(int x,int y){
    int a=find(x);
    int b=find(y);
    if(a==b&&rl[y]-rl[x]!=t){ans++; return ;}
    f[b]=a;
    rl[b]=rl[x]-rl[y]+t;
}

int main(){
    while(~scanf("%d%d",&n,&m)){
        rep(i,1,n)f[i]=i;
        rep(i,1,m){
            scanf("%d%d%d",&a,&b,&t);
            un(--a,b);
        }
        printf("%d",ans);
    }
    return 0;
}