[HNOI2005]狡猾的商人

惊奇地发现，如果一个区间能被判定是错的，当且仅当这个区间被已知权值的区间夹着，且表出的区间值与给出的不相等，才能表示这个区间GG了。

然后用带权并查集维护当前节点所能表示的最远区间及其权值。如果发现新的区间的find(l-1)==find(r)，就可以猜猜看它的正确性了。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=105;
int T,n,m,fa[N],dis[N];
int find(int x) {
    if(x!=fa[x]) {
        int fx=fa[x];
        fa[x]=find(fa[x]);
        dis[x]+=dis[fx];
    }
    return fa[x];
}
void solve() {
    scanf("%d%d",&n,&m);
    for(int i=0;i<=n;i++) fa[i]=i,dis[i]=0;
    bool flag=0;
    for(int i=1,l,r,c;i<=m;i++) {
        scanf("%d%d%d",&l,&r,&c);
        if(flag) continue;
        int fx=find(l-1),fy=find(r);
        if(fx^fy) {
            dis[fy]=-dis[r]+dis[l-1]-c;
            fa[fy]=fx;
        }
        else if(!(fx^fy)) {if(dis[r]-dis[l-1]!=-c) flag=1;}
    }
    puts(flag?"false":"true");
}
int main() {
    scanf("%d",&T);
    while(T--) solve();
}