Description

现有一个传动系统，包含了N个组合齿轮和M个链条。每一个链条连接了两个组合齿轮u和v，并提供了一个传动比x 

: y。即如果只考虑这两个组合齿轮，编号为u的齿轮转动x圈，编号为v的齿轮会转动y圈。传动比为正表示若编号

为u的齿轮顺时针转动，则编号为v的齿轮也顺时针转动。传动比为负表示若编号为u的齿轮顺时针转动，则编号为v

的齿轮会逆时针转动。若不同链条的传动比不相容，则有些齿轮无法转动。我们希望知道，系统中的这Ｎ个组合齿

轮能否同时转动。

Input

有多组数据，第一行给定整数Ｔ，表示总的数据组数，之后依次给出Ｔ组数据。每一组数据的第一行给定整数Ｎ和

Ｍ，表示齿轮总数和链条总数。之后有Ｍ行，依次描述了每一个链条，其中每一行给定四个整数u，v，x和y，表示

只考虑这一组联动关系的情况下，编号为u的齿轮转动x圈，编号为v的齿轮会转动y圈。请注意，x为正整数，而y为

非零整数，但是y有可能为负数。

T<=32，N<=1000，M<=10000且x与y的绝对值均不超过100

Output

输出T行，对应每一组数据。首先应该输出标识这是第几组数据，参见样例输出。之后输出判定结果，如果N个组合

齿轮可以同时正常运行，则输出Yes，否则输出No。

Sample Input

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

Sample Output

Case #1: Yes

Case #2: No

Solution 

裸的加权并查集……开个$g[i]$表示$i$和并查集根的转速比率即可……

Code

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #define N (1009) 6 using namespace std; 7  8 int n,m,T,flag,u,v,x,y,fa[N]; 9 double g[N];10 11 int Find(int x)12 {13     if (x==fa[x]) return x;14     int f=Find(fa[x]);15     g[x]*=g[fa[x]]; return fa[x]=f;16 }17 18 int main()19 {20     scanf("%d",&T);21     for (int t=1; t<=T; ++t)22     {23         flag=1;24         scanf("%d%d",&n,&m);25         for (int i=1; i<=n; ++i) fa[i]=i,g[i]=1;26         for (int i=1; i<=m; ++i)27         {28             scanf("%d%d%d%d",&u,&v,&x,&y);29             int fu=Find(u), fv=Find(v);30             31             double k=1.0*x/y*g[v]/g[u];32             33             if (fu!=fv) fa[fu]=fv,g[fu]*=k;34             else if (fabs(1.0*x/y-g[u]/g[v])>1e-10) flag=0;35         }36         if (flag) printf("Case #%d: Yes\n",t);37         else printf("Case #%d: No\n",t);38     }39 }