\(\\\)
对于一个长度为\(N\)的数列，以\(L_i,R_i,Sum_i\)的形式给出\(M\)个区间和，判断是否存在一个能够满足所有区间和的合法数列，多组数据。
- \(N\in [0,100]\)，\(M\in [0,1000]\)，数据组数\(\le 100\)
\(\\\)
\(Solution\)
- 带偏移量的并查集，将区间和转为前缀和相减，到根节点距离即为两前缀和之差。
对于不属于一个连通块的\(L_i,R_i\)，合并父节点\(F_l,F_r\)时，\(F_l\)到\(F_r\)的距离为\(V_{R_i}-(V_{L_i}-Sum)\)
对于属于一个连通块的\(L_i,R_i\)，\(find\)的过程中已经更新了到根节点的距离，所以相减即可验证答案，注意向右合并和向左合并相减的关系可能会相反，可以手画理解一下。
\(\\\)
\(Code\)
#include#include #include #include #include #include #include #define N 110#define R register#define gc getcharusing namespace std; int f[N],v[N];inline void reset(int n){ for(R int i=0;i<=n;++i) f[i]=i,v[i]=0;}int find(int x){ if(x==f[x]) return x; int fa=find(f[x]); v[x]+=v[f[x]]; return f[x]=fa;} inline int rd(){ int x=0; bool f=0; char c=gc(); while(!isdigit(c)){if(c=='-')f=1;c=gc();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();} return f?-x:x;} int main(){ int t=rd(),n,m; while(t--){ n=rd(); m=rd(); reset(n); bool fl=0; for(R int i=1,x,y,w;i<=m;++i){ x=rd()-1; y=rd(); w=rd(); int fx=find(x),fy=find(y); if(fx!=fy){f[fx]=fy;v[fx]=v[y]-v[x]+w;} else if(v[x]-v[y]!=w) fl=1; } puts(fl?"false":"true"); } return 0;}