狡猾的商人
知识点:维护到祖宗节点距离的并查集
对于本题,我们使用维护到祖宗节点距离的并查集。其基础模板如下
int p[N], d[N];
//p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离
// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x)
{
int u = find(p[x]);
d[x] += d[p[x]];
p[x] = u;
}
return p[x];
}
// 初始化,假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
{
p[i] = i;
d[i] = 0;
}
// 合并a和b所在的两个集合:
p[find(a)] = find(b);
d[find(a)] = distance; // 根据具体问题,初始化find(a)的偏移量
那么,对于本体来说最为困难的是:如何确定合并两个集合时更新到祖宗节点距离的更新方式。我们不妨先来看这样一个例子,现有结点$1,2,3,4$,有$p[1]=3,p[2]=4,d[1]=10,d[2]=30$,即如下图所示
现我们要添加一条边$1 \mathop{\rightarrow}\limits^{w} 2$,即$p[find(1)]=find(2) \Rightarrow p[3]=4$。根据图示可以很容易得出$d[3]=w(3 \rightarrow 1)+w(1 \rightarrow 2)+w(2 \rightarrow 4)=-d[1]+w+d[2]$。由此我们可以推断出,如果要添加一条边$x \mathop{\rightarrow}\limits^w y (x<y)$ (将$x$合并到$y$),距离更新方式如下$d[find(x)] = -p[x]+w+d[y]$。如果要添加的这条边的两个端点已经位于同一个集合中,则直接判断$d[x]-d[y] (x<y)$是否与$w$相等即可,如果不相等则可判定当前账本存在问题。
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int T, n, m;
int p[N], pre[N];
bool res = false;
int find(int x) {
if (x != p[x]) {
int t = find(p[x]);
pre[x] += pre[p[x]];
p[x] = t;
}
return p[x];
}
void combine(int a, int b, int c) {
int pa = find(a), pb = find(b);
if (pa != pb) {
p[pa] = pb;
pre[pa] = pre[b] - pre[a] + c;
} else {
if (pre[a] - pre[b] != c)
res = true;
}
}
int main() {
cin >> T;
while (T--) {
res = false;
cin >> n >> m;
for (int i = 0; i <= n; i++) p[i] = i,pre[i]=0;
while (m--) {
int a, b, c;
cin >> a >> b >> c;
combine(a - 1, b, c);
if (res) break;
}
if (res) cout << "false" << endl;
else cout << "true" << endl;
}
return 0;
}
很详细的并查集!
能帮到您就好。