By AHdoc命题 鸣谢Loi_DQS上传

首先可以看出这个齿轮的转动关系是具有传递性的，如果知道x和y的关系，也知道y和z的关系，就可以推出x和z的关系。具有这种关系的东西一般都可以用加权并查集来搞。对于每个元素给它维护一个dis[x]，表示的含义是如果x的代表元素转动1圈，x要转动几圈。每次读入一个限制如果x和y不在同一个集合里就进行合并。合并的时候先找到x的代表元素r1和y的代表元素r2，然后我们要把r2合并到r1上。要进行合并就要知道r1转一圈的时候r2转几圈。设从读入的信息可以知道x转一圈的时候y转w圈，那么如果r1转了一圈，y就转了dis[x]∗w圈；而当y转了dis[x]∗w圈的时候，r2转了dis[x]∗w/dis[y]圈。关系如下图：
 
如果读入的x和y在一个集合里，那么就可以用维护的信息算出x转了一圈的时候y转了几圈，和读入的信息进行比对就可以判定是否发生矛盾。

这个数据范围看起来好像很小的样子。。但是如果它出上n-1个信息，每次都是当齿轮i转动1圈的时候齿轮i+1转动100圈，那么最后就会发现当齿轮1转动一圈的时候齿轮n会转动100n圈。。这样的话就不能直接用int或者long long或者什么类似的东西来维护加权并查集的dis了。。用分解质因数似乎是比较稳的方法，但是听说用long double还是什么类似的东西也能过？

#include<cmath>#include<cstdio>using namespace std;typedef double real;inline void read(int &x){    register char ch=getchar();int f=1;x=0;    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘) f=-1;ch=getchar();}    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}    x*=f;}const int N=1e5+5;const real eps=1e-6;int T,n,m,cas;bool flag;int fa[N];real dis[N];int find(int x){    int t;    if(fa[x]!=x) t=find(fa[x]),dis[x]*=dis[fa[x]],fa[x]=t;    return fa[x];}int main(){    for(read(T);T--;flag=0){        read(n);read(m);        for(int i=1;i<=n;i++) fa[i]=i,dis[i]=1;         for(int i=1,r1,r2,u,v,x,y;i<=m;i++){            read(u);read(v);read(x);read(y);            r1=find(u);r2=find(v);            if(r1==r2){                if(fabs(dis[v]/dis[u]-(real)y/(real)x)>eps){                    flag=1;break;                }            }            else{                fa[r2]=r1;                dis[r2]=(dis[u]*y)/(dis[v]*x);            }        }        printf("Case #%d: %s\n",++cas,flag?"No":"Yes");    }    return 0;}