复习了一下边带权并查集板子。
设 \(d_{x}\) 表示当前点到它所在连通块根节点的距离。
合并点 \(x\) 和点 \(y\) 所在两个连通块时需要更新 \(d\)。因为将 \(x\) 点所在连通块的根节点的父亲节点设为了 \(y\) 点所在连通块的根节点，所以有 \(x \to y \to Find(y)=x \to Find(x) \to Find(y)\)，更新 \(d_{Find(x)}=d_{y}+z-d_{x}\)，其中 \(z\) 是 \(x\) 点到 \(y\) 点的距离。
路径压缩的时候也需要更新 \(d\)，直接将 \(d_{x}\) 加上 \(d_{fa_{x}}\) 即可。
\(i\) 可以被加入集合 \(S\)，当且仅当当前的 \(x\) 和 \(y\) 不在一个连通块或者 \(x\) 到 \(y\) 的距离为 \(z\)。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3f
#define inf_db 127
#define ls id << 1
#define rs id << 1 | 1
#define re register
#define endl '\n'
typedef pair <int,int> pii;
const int MAXN = 2e5 + 10;
int n,q,x,y,z,d[MAXN],fa[MAXN],ans[MAXN],cnt;
inline int Find(int x)
{
if(x == fa[x]) return x;
int f = fa[x];
fa[x] = Find(fa[x]),d[x] += d[f];
return fa[x];
}
signed main()
{
cin >> n >> q;
for(int i = 1;i <= n;i++) fa[i] = i;
for(int i = 1;i <= q;i++)
{
cin >> x >> y >> z;
int fx = Find(x),fy = Find(y);
if(fx != fy)
fa[fx] = fy,d[fx] = d[y] - d[x] + z,ans[++cnt] = i;
else if(d[x] - d[y] == z)
fa[fx] = fy,d[fx] = d[y] - d[x] + z,ans[++cnt] = i;
}
for(int i = 1;i <= cnt;i++) cout << ans[i] << " ";
return 0;
}