【洛谷-P4079】[SDOI2016]齿轮 • TonyYin's Blog

题意#

给定 $n$ 个齿轮和个 $m$ 个链条，每个链条连接两个齿轮 $u, v$ ，并且有一个传动比。

传动比有两个参数 $x, y$ ，表示在单位时间内，若 $u$ 转动 $x$ 圈，则 $v$ 必须转动 $y$ 圈。

问 $n$ 个齿轮能否同时转动。

分析#

考虑到所有链条的传动比都已经给出，我们如果随便找一个齿轮，固定他的转速，那么所有与他有关的齿轮速度就都是固定的了。

所以我们把链条两侧的点连双向边，每条边存储传动比。对于每个联通块，随便找一个点，固定其转速，之后求出所有与其相连的点的转速，再判断是否产生矛盾。

题目卡精度，所以在固定第一个点的转速时，可以定为 $100$ 或 $1000$ ，运算过程中比较大小需要用到 $\epsilon$ 解决精度问题。BJEA123456

具体实现上，只需要循环一遍，对每个点都 DFS 一遍，判断是否产生了矛盾就可以了。

代码#

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 10, MAXM = 2e5 + 10;
const double eps = 1e-5;
int T, n, m;
struct Edge{
    int to, nxt, x, y;
}edge[MAXM];
int head[MAXN], cnt = 0;
void add(int u, int v, int x, int y) {
    edge[++cnt].to = v;
    edge[cnt].x = x;
    edge[cnt].y = y;
    edge[cnt].nxt = head[u];
    head[u] = cnt;
}
double vel[MAXN];
bool dfs(int x) {
    for(int i = head[x]; i; i = edge[i].nxt) {
        int v = edge[i].to;
        if(fabs(vel[v]) < eps) {// if(vel[v] == 0)
            vel[v] = vel[x] * (edge[i].y) / (double)(edge[i].x);
            if(!dfs(v)) return false;
        }
        if(fabs(vel[v] - vel[x] * (edge[i].y) / (double)(edge[i].x)) > eps) 
            // if(vel[v] != vel[x] * edge[i].y / edge[i].x)
            return false;
    }
    return true;
}
int main() {
    scanf("%d", &T);
    for(int t = 1; t <= T; t++) {
        scanf("%d%d", &n, &m);
        memset(head, 0, sizeof(head)); cnt = 0;
        memset(vel, 0, sizeof(vel));
        for(int i = 1; i <= m; i++) {
            int a, b, x, y; scanf("%d%d%d%d", &a, &b, &x, &y);
            add(a, b, x, y); add(b, a, y, x);//注意 反向边的转速比也要反过来
        }
        bool ok = true;
        for(int i = 1; i <= n; i++) {
            if(fabs(vel[i]) < eps) {
                vel[i] = 100;
                if(!dfs(i)) {
                    ok = false; break;
                }
            }
        }
        printf("Case #%d: %s\n", t, (ok)?"Yes":"No");
    }
    return 0;
}

cpp