Luogu – P4079 – [SDOI2016]齿轮

题意

给定 $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;
}
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇