P2294. 狡猾的商人

发表于 2023-11-13 分类于洛谷阅读次数： Waline：本文字数： 266 阅读时长 ≈ 1 分钟

考点

边带权并查集

题解

#include <bits/stdc++.h>
using namespace std;
const int LEN = 1e5 + 50;
int n, m, fa[LEN], dis[LEN];

int find(int x) {
  if (fa[x] == x) return x;
  int anc = fa[x];
  fa[x] = find(fa[x]);
  dis[x] += dis[anc];
  return fa[x];
}

void join(int x, int y, int w) {
  int a = find(x), b = find(y);
  fa[a] = b;
  dis[a] = dis[y] + w - dis[x];
}

void work() {
  bool flag = true;
  int x, y, w;
  cin >> n >> m;
  for (int i = 0; i <= n; ++i) fa[i] = i, dis[i] = 0;
  while (m--) {
    cin >> x >> y >> w;
    --x;
    if (find(x) != find(y)) {
      join(x, y, w);
    } else {
      if (dis[x] - dis[y] != w) {
        flag = false;
      }
    }
  }
  flag ? puts("true") : puts("false");
}

int main() {
  int t;
  cin >> t;
  while (t--) work();
  return 0;
}