自动搬运

查看原文

来自洛谷，原作者为

	aiyougege **

搬运于2025-08-24 21:56:15，当前版本为作者最后更新于2018-07-01 16:54:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

可算是被我自己的sb并查集水平给坑了 用并查集做只是因为这个题的标签中有并查集的标签

Solution

如果将齿轮看做点, 链条看做边, 那么发现当其不形成环时总是合法的; 换言之, 只要形成了环, 我们就要判断是否合法.

发现传动比具有传递性, 即如果$a,b$的传动比为$w$,$b,c$的传动比为$e$, 那么$a,c$的传动比为$we$.

考虑并查集的做法:

• 若用链条联通$a,b$两个齿轮
• 如果未联通, 则用并查集合并
• 若联通, 设从$a$经过一系列路径传动到$b$的传动比为$\alpha$, $a$和$b$直接联通的传动比为$\beta$, 若$\alpha\ne\beta$则不合法.

如何求出两个齿轮间接连接的传动比呢? 可以这么做:

• 用$g_i$表示$i$于其集合的祖先的传动比.
• 那么$g_i/g_j$就是两个点$i,j$之间的传动比.

至于如何利用并查集维护这个$g_i$, 请学习所谓的"带权并查集".反正我自己写过的带权并查集都是YY出来的.

不得不说带权并查集真的好多细节, 而普通并查集不用管那么多……

Code

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#define N 1005
#define eps 1e-9
using namespace std;

int f[N];double g[N];

int find(int x){
    if(f[x]==x)return x;
	int temp=find(f[x]);
	g[x]*=g[f[x]];
    return f[x]=temp;
}

bool equal(double a,double b){return fabs(a-b)<=eps;}

int main(){
    int T,n,m,a,b;double x,y;bool flag=0;
    scanf("%d",&T);
    for(int t=1;t<=T;++t){
        scanf("%d%d",&n,&m);flag=0;
        for(int i=1;i<=n;++i)f[i]=i;
        for(int i=1;i<=n;++i)g[i]=1;
        for(int i=1;i<=m;++i){
            scanf("%d%d%lf%lf",&a,&b,&x,&y);
			int f1=find(a),f2=find(b);
            if(f1==f2){
                if(!equal(x/y,g[a]/g[b])){flag=true;}
            }
            else f[f2]=f1,g[f2]*=g[a]/g[b]*y/x;
        }
        if(flag)printf("Case #%d: No\n",t);
        else printf("Case #%d: Yes\n",t);
    }
    return 0;
}