题目描述
链接：https://ac.nowcoder.com/acm/contest/5505/A来源：牛客网
现有一个传动系统，包含了N个组合齿轮和M个链条。每一个链条连接了两个组合齿轮u和v，并提供了一个传动比x : y。
即如果只考虑这两个组合齿轮，编号为u的齿轮转动x圈，编号为v的齿轮会转动y圈。传动比为正表示若编号为u的齿轮顺时针转动，则编号为v的齿轮也顺时针转动。传动比为负表示若编号为u的齿轮顺时针转动，则编号为v 的齿轮会逆时针转动。若不同链条的传动比不相容，则有些齿轮无法转动。我们希望知道，系统中的这Ｎ个组合齿轮能否同时转动。
输入描述:
有多组数据，第一行给定整数Ｔ，表示总的数据组数，之后依次给出Ｔ组数据。每一组数据的第一行给定整数Ｎ和Ｍ，表示齿轮总数和链条总数。之后有Ｍ行，依次描述了每一个链条，其中每一行给定四个整数u，v，x和y，表示只考虑这一组联动关系的情况下，编号为u的齿轮转动x圈，编号为v的齿轮会转动y圈。请注意，x为正整数，而y为非零整数，但是y有可能为负数。T ≤ 32，N ≤ 1000，M ≤ 10000且x与y的绝对值均不超过100
输出描述:
输出T行，对应每一组数据。首先应该输出标识这是第几组数据，参见样例输出。之后输出判定结果，如果N个组合齿轮可以同时正常运行，则输出Yes，否则输出No。
示例1
输入
[复制]
2
3 3
1 2 3 5
2 3 5 -7
1 3 3 -7
3 3
1 2 3 5
2 3 5 -7
1 3 3 7
输出
[复制]
Case #1: Yes
Case #2: No
思路
由于是判断集合之间关系，很容易想到用带权的并查集来做。
d[u]表示u是祖先节点的几倍。从1开始遍历链条，如果两个齿轮u,v之前不是同一个集合，则要将两个集合合并，让x的祖先节点的倍数转换：(u/fa[u]=d[u],v/fa[v]=d[v],u/v=x/y),所以(d[fa[u]]=d[v]*(x/y)/d[u]).
在路径压缩时也要考虑转换d。
代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const double EPS=1e-8;
const int N=1010;
int fa[N];
double d[N];
int Find(int x){
if(fa[x]==x) return x;
int ft=Find(fa[x]);
d[x]=d[x]*d[fa[x]];
return fa[x]=ft;
}
int main(){
int T;
cin>>T;
for(int cas=1;cas<=T;++cas){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;++i) fa[i]=i,d[i]=1;
bool f=1;
for(int i=1;i<=m;++i){
int u,v;
double x,y;
cin>>u>>v>>x>>y;
int fu=Find(u),fv=Find(v);
if(fu!=fv){
fa[fu]=fv;
d[fu]=d[v]*(x/y)/d[u];
}
else {
if(fabs(d[u]/d[v]-x/y)>EPS) f=0;
}
}
cout<<"Case #"<<cas<<": ";
if(f) puts("Yes");
else puts("No");
}
return 0;
}