题解： P4079 [SDOI2016] 齿轮

Chenyichen0420 · 2025-05-22 16:06:27 · 题解

思路分析

很简单，就不停的从不同的地方假定转速是 1，并暴搜检验是否满足要求就行了。说实话值不到蓝。

但是显然，如果我们直接拿 long double 等的去暴力维护的话，很容易就爆精度了。

所以有两种解法：一种是多找几个大质数，用逆元等的等价分数类来比较，另一种是使用 \log，把乘法“降阶”为加法。我采用的是第二种。

注意处理符号，代码如下：

#include<bits/stdc++.h>
using namespace std;
int t, n, m;
struct node {
    int p, t; double v;
    node(int pi, double vi, int ty) :p(pi), v(vi), t(ty) {};
}; vector<node>son[1005];
double ras[1005]; bool tas[1005], vis[1005];
inline bool eq(double l, double r) {
    return abs(r - l) <= 1e-6;
}
inline void dfs(int p, double v, bool ty) {
    ras[p] = v; tas[p] = ty; vis[p] = 1;
    for (const node& sp : son[p])
        if (!vis[sp.p]) dfs(sp.p, v + sp.v, ty ^ sp.t);
        else if ((ty ^ sp.t) != tas[sp.p] || !eq(ras[sp.p], sp.v + v)) {
            throw 114514;
        }
}
inline double mylog(int v) {
    return log(abs(v)) * 1000;
}
signed main() {
    ios::sync_with_stdio(0); cin >> t;
    for (int tt = 1; tt <= t; ++tt) {
        cin >> n >> m;
        for (int i = 1, l, r, a, b; i <= m; ++i)
            cin >> l >> r >> a >> b,
            son[l].emplace_back(r, mylog(b) - mylog(a), a * b < 0),
            son[r].emplace_back(l, mylog(a) - mylog(b), a * b < 0);
        memset(vis, 0, sizeof vis);
        try {
            for (int i = 1; i <= n; ++i)
                if (!vis[i]) dfs(i, 0, 0);
            cout << "Case #" << tt << ": Yes\n";
        }
        catch (...) {
            cout << "Case #" << tt << ": No\n";
        }
        for (int i = 1; i <= n; ++i) son[i].clear();
    }
}