P4079 [SDOI2016]齿轮 题解

· · 题解

原题

题意

给出 N 个组合齿轮和 M 个链条，每个链条连接两个齿轮，如果两个齿轮的转动比不相容，则两个齿轮无法同时转动。请判断 N 个齿轮最终是否能都转动。

做法

看到这类判断是否成环的题目，不难想到并查集，而这题又要考虑到费用，所以带权并查集自然是一个很好的选择。

定义 g_i 为传递到第 i 个齿轮的转动比之积，所以 g_u/g_v 就表示 第 u 个齿轮到第 v 个齿轮的转动比之积。

那么如果 u 和 v 位于同一联通块，此时就出现了环，就需要判断 g_u/g_v 是否和 x/y 相等。

否则就需要在 u 和 v 之间连一条边，这条边的权值为 (x*g_v)/(y*g_u)，这里解释一下，设这条边的权值为 z，易知 z*(g_u/g_v)=x/y，解得z=(x*g_v)/(y*g_u)。

然后再讲一下这题的坑点

  1. 因为是带权并查集，所以在传递权值以及父亲时要先递归再操作。
  2. 因为是实数计算，所以要考虑精度。

代码

#include<cstdio>
#include<algorithm>
#include<cmath>
#define N 1005
#define eps 1e-10

using namespace std;

int T,n,m,cnt;
int f[N];
double g[N];
bool fl;

int find(int x){
    if(f[x]==x) return x;
    int fa=find(f[x]); 
    g[x]*=g[f[x]];
    return f[x]=fa;
} // 带权并查集 

inline void clear(){
    fl=0;
    for(int i=0;i<=N;i++){
        f[i]=i;
        g[i]=1.00;
    }
} // 清空数组 

int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        int u,v;
        double x,y;
        clear();
        for(int i=1;i<=m;i++){
            scanf("%d%d%lf%lf",&u,&v,&x,&y);
            int fu=find(u),fv=find(v); // 找爹 
            if(fu!=fv){ // 不成环的情况 
                f[fu]=fv;
                g[fu]*=(x*g[v])/(y*g[u]);
            } // 路径压缩 
            else // 成环的情况 
                if(fabs(g[u]/g[v]-x/y)>eps) fl=1; // 判断传动比是否相容
        }
        ++cnt;
        if(!fl) printf("Case #%d: Yes\n",cnt);
        else printf("Case #%d: No\n",cnt);
    }
    return 0;
}