[ HNOI 2005 ] 狡猾的商人
\(\\\)
\(Description\)
对于一个长度为\(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<cmath>
#include<cctype>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 110
#define R register
#define gc getchar
using 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;
}1、PAT Gas Station (30)
2、Jsonp的使用
3、Tinyshell: 一个简易的shell命令解释器
4、CVS, Automake与Autoconf简介
5、信息安全等级合规测评