题解 P4079 【[SDOI2016]齿轮】

aiyougege · 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;
}