带权并查集 gcd
#include <iostream>
#include <cstring>
#define x first
#define y second
using namespace std;
using LL = long long;
using PII = pair<LL, LL>;
constexpr int N = 1010;
int T, n, m;
int f[N];
PII rate[N]; // f / a = rate[a].x / rate[a].y
LL gcd(LL a, LL b)
{
if (!b) return a;
return gcd(b, a % b);
}
PII mkp(LL a, LL b)
{
LL g = gcd(a, b);
return {a / g, b / g};
}
int find(int x)
{
if (f[x] != x)
{
int p = find(f[x]);
rate[x] = mkp(rate[x].x * rate[f[x]].x, rate[x].y * rate[f[x]].y);
f[x] = p;
}
return f[x];
}
bool merge(int a, int b, int x, int y)
{
int pa = find(a), pb = find(b);
if (pa == pb)
{
if (rate[b].x * rate[a].y * y != rate[b].y * rate[a].x * x)
return false;
}else
{
f[pa] = pb;
rate[pa] = mkp(rate[b].x * rate[a].y * y, rate[b].y * rate[a].x * x);
}
return true;
}
int main()
{
cin >> T;
for (int t = 1; t <= T; ++ t)
{
cin >> n >> m;
for (int i = 1; i <= n; ++ i)
{
f[i] = i;
rate[i] = {1, 1};
}
int a, b, x, y;
bool flag = true;
while (m --)
{
cin >> a >> b >> x >> y;
flag &= merge(a, b, x, y);
}
if (flag)
printf("Case #%d: Yes\n", t);
else
printf("Case #%d: No\n", t);
}
return 0;
}