前置芝士

并查集思想

[find]

[python]

#python while
def find(x:int)->int:
	while x!=fa[x]:
		x=fa[x]=fa[fa[x]]
	return x

#python 递归
def find(x:int)->int:
	if fa[x]!=x:
		fa[x]=find(fa[x])
	return fa[x]

[c++]

//c++ while lambda  
/*function<int(int)> find=[&](int x){}   */
    auto find=[&](int x){
        while(x!=fa[x]) x=fa[x]=fa[fa[x]];
        return x;
    };

带权并查集

狡猾的商人

【题目描述】

刁姹接到一个任务，为税务部门调查一位商人的账本，看看账本是不是伪造的。账本上记录了 n 个月以来的收入情况，其中第 i 个月的收入额为 a_i，i=1,2,…,n−1,n。当 ai>0 时表示这个月盈利ai元，当ai<0 时表示这个月亏损ai元。所谓一段时间内的总收入，就是这段时间内每个月的收入额的总和。刁姹的任务是秘密进行的，为了调查商人的账本，她只好跑到商人那里打工。她趁商人不在时去偷看账本，可是她无法将账本偷出来，每次偷看账本时她都只能看某段时间内账本上记录的收入情况，并且她只能记住这段时间内的总收入。

现在，姹总共偷看了m 次账本，当然也就记住了m 段时间内的总收入，你的任务是根据记住的这些信息来判断账本是不是假的。

【输入描述】

第一行为一个正整数 w，其中 w<100，表示有 w 组数据，即 w 个账本，需要你判断。

每组数据的第一行为两个正整数 n 和 m，其中 n<100,m<1000，分别表示对应的账本记录了多少个月的收入情况以及偷看了多少次账本。

接下来的 m 行表示刁姹偷看 m 次账本后记住的 m 条信息，每条信息占一行，有三个整数 s,t 和 v，表示从第 s 个月到第 t 个月（包含第 t 个月）的总收入为 v，这里假设 s 总是小于等于 t。

【输出描述】

包含 w 行，每行是 true 或 false，其中第 i 行为 true 当且仅当第 i 组数据，即第 i 个账本不是假的；第 i 行为 false 当且仅当第 i 组数据，即第 i 个账本是假的。

【解题思路】

如何确定合并两个集合时更新到祖宗节点距离的更新方式。

我们不妨先来看这样一个例子，现有结点1,2,3,4有p[1]=3,p[2]=4,d[1]=10,d[2]=30。

d[3]=w(3→1)+w(1→2)+w(2→4)=−d[1]+w+d[2]

如果要添加一条边x→wy(x<y)(将x合并到y)，距离更新方式如下d[find(x)]=−p[x]+w+d[y]。

如果要添加的这条边的两个端点已经位于同一个集合中，则直接判断d[x]−dy是否与w相等即可，如果不相等则可判定当前账本存在问题。

最后注意一点 从s到t月份的金钱不是sum[t]-sum[s]（这是算得s+1到t的金钱），应该是sum【t】-sum【s-1】 （前缀和思想）。

int fa[1010],sum[1010],n,m,flag;
int find(int x){
	if(fa[x]==x) return fa[x];
	int tmp=find(fa[x]);
	sum[x]+=sum[fa[x]];
	return fa[x]=tmp;
}
void merge(int x,int y,int z){
	int fx,fy;
	fx=find(x);
	fy=find(y);
	if(fx!=fy){
		fa[fy]=fx;
		sum[fy]=sum[x]-sum[y]+z;
	}else{
		if(sum[y]-sum[x]!=z)
			flag=true;
	}
}
void init(int n){
	for(int i=0;i<=n;i++){
		fa[i]=i;
		sum[i]=0;
	}
	flag=false;
}
void solve(){
	int x,y,z;
	cin>>n>>m;
	init(n);
	for(int i=1;i<=m;i++){
		cin>>x>>y>>z;
		x--;
		merge(x,y,z);
	}
	if(flag) cout<<"false"<<endl;
	else cout<<"true"<<endl;
}