P4079 [SDOI2016]齿轮

StarPatrick · 2022-02-19 15:34:47 · 题解

可以发现，一个齿轮转动会带动其他齿轮转动，那么其他齿轮转动的时候又让这个齿轮转动，一个齿轮是不能拥有两个转速的，所以如果这两个转速不同，就是 No，否则 Yes。

那么我们可以把齿轮看成点，转速比看成边权，那么一个点的点权就为这个点的转速，当前点的点权乘以边权就为下一个点的点权，这样我们就可以建一个双向图进行搜索遍历，第一次遍历到的点权和之后遍历到的点权比较（这里注意一下精度），就 ok 了。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
int t, n, m;
bool f;
struct e
{
    int i;
    double u;
};
vector<e> v[1005];
double book[1005];
void dfs(int i, double u)
{
    for (int p=0;p<v[i].size();p++)
    {
        double x = v[i][p].u*u;
        if (fabs(book[v[i][p].i])<=1e-5)
        {
            book[v[i][p].i] = x;
            dfs(v[i][p].i, x);
            if (f)
            {
                return ;
            }
        }
        else if (fabs(book[v[i][p].i]-x)>1e-5)
        {
            f = 1;
            return ;
        }
    }
}
signed main()
{
    scanf("%d", &t);
    for (int zqw=1;zqw<=t;zqw++)
    {
        f = 0;
        scanf("%d %d", &n, &m);
        for (int p=1;p<=n;p++)
        {
            v[p].clear();
            book[p] = 0;
        }
        for (int p=1;p<=m;p++)
        {
            int u, s, x, y;
            scanf("%d %d %d %d", &u, &s, &x, &y);
            if (y>0)
            {
                v[u].push_back({s, y*1.0/x});
                v[s].push_back({u, x*1.0/y});
            }
            else
            {
                v[s].push_back({u, x*1.0/y});
                v[u].push_back({s, y*1.0/x});
            }
        }
        for (int p=1;p<=n;p++)
        {
            if (fabs(book[p])<=1e-5)
            {
                book[p] = 1.0;
                dfs(p, 1.0);
            }
            if (f)
            {
                break;
            }
        }
        if (!f)
        {
            printf("Case #%d: Yes\n", zqw);
        }
        else
        {
            printf("Case #%d: No\n", zqw);
        }
    }
    return 0;
}