P4079 [SDOI2016]齿轮题解

Harry_Hedwig · 2022-02-19 13:12:19 · 题解

先看题。

现有一个传动系统，包含了 N 个组合齿轮和 M 个链条。每一个链条连接了两个组合齿轮 u 和 v，并提供了一个传动比 x:y。即如果只考虑这两个组合齿轮，编号为 u 的齿轮转动 x 圈，编号为 v 的齿轮会转动 y 圈。传动比为正表示若编号为 u 的齿轮顺时针转动，则编号为 v 的齿轮也顺时针转动。传动比为负表示若编号为 u 的齿轮顺时针转动，则编号为 v 的齿轮会逆时针转动。若不同链条的传动比不相容，则有些齿轮无法转动。我们希望知道，系统中的这 N 个组合齿轮能否同时转动。

题目给出的信息很明确，一个齿轮动会带动其他齿轮一起动，既然如此，这个就很像多米诺骨牌了。而我们想起原来的一个与多米诺骨牌有关的问题是使用图论解决的，因此我们想到它有可能也和图论有关。

既然是图论，那么我们肯定需要知道边权和什么有关。由于题目条件，我们已知编号为 u 的齿轮转动 x 圈，编号为 v 的齿轮会转动 y 圈，所以当编号为 u 的齿轮转动 a 圈时，编号为 v 的齿轮会转动 a\times \frac{y}{x} 圈。

因此我们不妨让编号为 u 的齿轮转动 1 圈，编号为 v 的齿轮转动 \frac{y}{x} 圈。

那么此时我们会发现一部分（整个系统不一定是完全连通的！）的齿轮被其中的一些链条相连组成了一个图，其中几个齿轮可能会有不同的到达方式，但是我们要保证它的转动圈数不变才能使这个系统可以正常运行（Yes）否则就会卡住（No）。

剩下的……交给图的遍历解决即可。

Code

#include<bits/stdc++.h>
const double deviation=1e-10;//可能有误差
using namespace std;
struct node
{
    double val;
    int go;
}t1;
vector<node>G[1005];//邻接表存储图
double laps[1005];//记忆是否遍历过它所存在的子系统
bool ergodic(int s)//广度遍历
{
    int i,z[1005];
    queue<int>q;
    q.push(s);
    while(!q.empty())
    {
        int a=q.front();
        q.pop();
        for(i=0;i<G[a].size();i++)
        {
            if(laps[G[a][i].go]==laps[0])//没走过
            {
                laps[G[a][i].go]=laps[a]*G[a][i].val;
                q.push(G[a][i].go);
            }
            else
            {
                if(fabs(laps[G[a][i].go]-laps[a]*G[a][i].val)>deviation)//判断转的圈数是否不变
                    return 0;
            }
        }
    }
    return 1;
}
int main()
{
    int n,m,i,j,O,u,v,t;
    double w1,w2;
    bool f;
    scanf("%d",&t);
    for(O=1;O<=t;O++)
    {
        f=1;
        scanf("%d %d",&n,&m);
        for(i=1;i<=n;i++)
            G[i].clear();
        memset(laps,0,sizeof(laps));//多组输入输出！
        for(i=1;i<=m;i++)
        {
            scanf("%d %d %lf %lf",&u,&v,&w1,&w2);
            t1.val=w2/w1;
            t1.go=v;
            G[u].push_back(t1);
            t1.val=w1/w2;
            t1.go=u;
            G[v].push_back(t1);
        }
        printf("Case #%d: ",O);
        for(i=1;i<=n&&f;i++)
        {
            if(laps[i]==laps[0])
            {
                laps[i]=1;
                f=ergodic(i);
            }
        }
        if(f)
            puts("Yes");
        else
            puts("No");
    }
    return 0;
}

P4079 [SDOI2016]齿轮 题解

Code

P4079 [SDOI2016]齿轮题解