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
之前一直沒有嘗試過帶權并查集的題目，雖然大一暑假就學過帶權并查集的問題。。
大意：有M個數，不知道它們具體的值，但是知道某兩個數之間（包括這兩個數）的所有數之和，現在給出N個這樣的區間和信息，需要判斷有多少個這樣的區間和與前邊已知的區間和存在矛盾。
一開始想還真不知道怎么聯想到并查集上的。后來想想，確實可以用并查集解決這個問題。但是需要注意兩點，一個是轉化父親節點之后距離父親節點的距離怎么算。另一個就是這個是一個閉區間，我們在處理的時候，閉區間不好處理就將它轉化成開區間，l–或者r++。其他人說這個題目還有一個坑點就是多組輸入，好在單組讀入我也是多組讀入。。
代碼如下：

#include<bits/stdc++.h> #define ll long long using namespace std;const int maxx=2e5+100; const int maxm=4e4+100; int f[maxx],dis[maxx]; int n,m;inline int getf(int u) {int x;if(u!=f[u]){x=getf(f[u]);dis[u]+=dis[f[u]];//處理轉換之后距離父親節點距離f[u]=x;}return f[u]; } inline int merge(int u,int v,int val) {int t1=getf(u);int t2=getf(v);if(t1==t2){if(abs(dis[u]-dis[v])==abs(val)) return 0;else return 1;}else{f[t1]=t2;dis[t1]=val+dis[v]-dis[u];return 0;} } int main() {int x,y,ans,value;while(~scanf("%d%d",&n,&m)){ans=0;for(int i=0;i<=n;i++) f[i]=i,dis[i]=0;while(m--){scanf("%d%d%d",&x,&y,&value);x--;if(merge(x,y,value)) ans++;}printf("%d\n",ans);}return 0; }

努力加油a啊，(^o)/~

總結

以上是生活随笔為你收集整理的How Many Answers Are Wrong HDU - 3038（带权并查集）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。