牛客算法周周练4A

发表于 分类于 ， ， 阅读次数： 本文字数： 2.3k 阅读时长 ≈ 2 分钟

时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld # 题目描述 现有一个传动系统，包含了N个组合齿轮和M个链条。每一个链条连接了两个组合齿轮u和v，并提供了一个传动比x : y。 即如果只考虑这两个组合齿轮，编号为u的齿轮转动x圈，编号为v的齿轮会转动y圈。传动比为正表示若编号为u的齿轮顺时针转动，则编号为v的齿轮也顺时针转动。传动比为负表示若编号为u的齿轮顺时针转动，则编号为v 的齿轮会逆时针转动。若不同链条的传动比不相容，则有些齿轮无法转动。我们希望知道，系统中的这Ｎ个组合齿轮能否同时转动。 # 输入描述: 有多组数据，第一行给定整数Ｔ，表示总的数据组数，之后依次给出Ｔ组数据。 每一组数据的第一行给定整数Ｎ和Ｍ，表示齿轮总数和链条总数。 之后有Ｍ行，依次描述了每一个链条，其中每一行给定四个整数u，v，x和y，表示只考虑这一组联动关系的情况下，编号为u的齿轮转动x圈，编号为v的齿轮会转动y圈。 请注意，x为正整数，而y为非零整数，但是y有可能为负数。 T ≤ 32，N ≤ 1000，M ≤ 10000且x与y的绝对值均不超过100 # 输出描述: 输出T行，对应每一组数据。首先应该输出标识这是第几组数据，参见样例输出。之后输出判定结果，如果N个组合齿轮可以同时正常运行，则输出Yes，否则输出No。 # 示例1 输入 

1
2
3
4
5
6
7
8
9
2
3 3
1 2 3 5
2 3 5 -7
1 3 3 -7
3 3
1 2 3 5
2 3 5 -7
1 3 3 7
输出 
1
2
Case #1: Yes
Case #2: No

做法

之前想复杂了，一直在想如何转化为图论，想连边的方式，最后想到了用转速比作为边权，那么我们的目的就是找一个环，环的所有边权的积不等于1，然后就陷入了死胡同了，取对数变成了0权回路的存在性判定，泛化为k权回路的判定，这里就走歪了 其实很简单，如果存在积不为1的回路，那么我们在dfs的时候讲边权转化为点权，就会出现一个点被赋不同的值的情况，这个做法也可以推广到k权回路上，

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

#include<bits/stdc++.h>
using namespace std;

bool eq(double x,double y){ return fabs(x-y) < 1e-6;}

bool dfs(vector<vector<int>>& edge,
         vector<vector<double>>& rate,
         vector<double>& speed,
         int current,
         double current_speed){
    
    if(speed[current]==0) speed[current] = current_speed;
    else if(eq(speed[current] , current_speed)) return true;
    else return false;
    
    for(int i=0;i<edge[current].size();i++){
        if(!dfs(edge,
                rate,
                speed,
                edge[current][i],
                current_speed*rate[current][i])
          ) return false;
    }
    return true;
}

int main(){
    int T;
    cin>>T;
    for(int times=1;times<=T;times++){
        int n,m;
        cin>>n>>m;
        vector<vector<int>> edge(n);
        vector<vector<double>> rate(n);
        vector<double> speed(n);
        for(int i=1;i<=m;i++){
            int u,v,x,y;
            cin>>u>>v>>x>>y;
            u--,v--;
            edge[u].push_back(v);
            edge[v].push_back(u);
            rate[u].push_back(1.0*y/x);
            rate[v].push_back(1.0*x/y);
        }
        bool rotate = true;
        for(int i=0;i<n;i++) {
            if(speed[i]!=0) continue;
            if(!dfs(edge,rate,speed,i,1)) rotate=false;
        }
        if(rotate) cout<<"Case #"<<times<<": Yes"<<endl;
        else cout<<"Case #"<<times<<": No"<<endl;
    }
}