传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4602
【题解】
对于每组齿轮(u, v)连边,权值为y/x(反向边x/y)
那么直接dfs计算一遍即可。
# include <math.h>
# include <stdio.h>
# include <string.h>
# include <algorithm>
// # include <bits/stdc++.h>using namespace std;typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 5e5 + ;
const int mod = 1e9+;# define RG register
# define ST staticint T, n, m;
int head[M], nxt[M], to[M], tot;
ld w[M];
inline void add(int u, int v, ld _w) {
++tot; nxt[tot] = head[u];
head[u] = tot; to[tot] = v; w[tot] = _w;
}bool vis[M];
ld v[M];inline bool dfs(int x, ld c) {
v[x] = c; vis[x] = ;
for (int i=head[x]; i; i=nxt[i]) {
if(!vis[to[i]]) {
if(dfs(to[i], c*w[i])) return ;
} else {
if(fabs(v[to[i]]-c*w[i]) > 1e-) return ;
}
}
return ;
}
inline void sol() {
memset(head, , sizeof head);
tot = ;
scanf("%d%d", &n, &m);
for (int i=; i<=m; ++i) {
int u, v, x, y; scanf("%d%d%d%d", &u, &v, &x, &y);
add(u, v, (ld)y/x);
add(v, u, (ld)x/y);
}
memset(vis, , sizeof vis);
for (int i=; i<=n; ++i) {
if(vis[i]) continue;
if(dfs(i, )) {
puts("No");
return;
}
}
puts("Yes");
}int main() {
int T; scanf("%d", &T);
for (int i=; i<=T; ++i) {
printf("Case #%d: ", i);
sol();
}
return ;
}