NYOJ 1276 机器设备【dfs】

- 日理万妓 2022-05-24 22:12 28阅读 0赞

## 机器设备 ##

#### 题目描述 ####

> Alpha 公司设计出一种节能的机器设备。它的内部结构是由 N 个齿轮组成。整个机器设备有  
> 一个驱动齿轮，当启动它时，它立即按 10,000 圈/小时转速顺时针转动，然后它又带动与它相切  
> 的齿轮反方向，即逆时针转动。齿轮之间互相作用，每个齿轮都可能驱动着多个齿轮，最终带动  
> 一个工作齿轮完成相应的任务 。  
> 在这套设备中，记录了每个齿轮的圆心坐标和齿轮半径。已知驱动齿轮位于（0,0），最终的  
> 工作齿轮位于（Xt, Yt）。  
> Alpha 公司想知道传动序列中所有齿轮的转速。所谓传动序列，即能量由驱动齿轮传送，最  
> 后到达工作齿轮的过程中用到的所有齿轮。能量传送过程是，在一个半径为 R，转速为 S 圈/每小  
> 时的齿轮的带动下，与它相切的半径为 R’的齿轮的转速为-S\*R/R\` 转/小时。负号的意思是， 表  
> 示按反方向转动。  
> 已知，机器设备中除了驱动齿轮以外，所有齿轮都可能被另外某个齿轮带动，并且不会出现  
> 2 个不同的齿轮带动同一个齿轮的情况。  
> 你的任务是计算整个传动序列中所有齿轮的能量之和。即所有齿轮转速的绝对值之和。

#### 输入 ####

> 第一行： T 表示以下有 T 组测试数据（1≤T ≤8）  
> 对每组测试数据：  
> 第 1 行： N Xt Yt （2≤N ≤1100）  
> 接下来有 N 行， Xi Yi Ri 表示 N 个齿轮的坐标和半径 i=1,2,….,N  
> （ -5000 ≤Xi ，Yi ≤ 5000 3 ≤ Ri ≤ 1000 ）

#### 输出 ####

> 每组测试数据，输出占一行，即所有齿轮转速的绝对值之和 在double范围内，输出整数部分

#### 样例输入 ####

> 1  
> 4 32 54  
> 0 30 20  
> 0 0 10  
> 32 54 20  
> \-40 30 20

#### 样例输出 ####

> 20000

#### 题意概括： ####

有n个齿轮，有一个驱动轮为起点，还有一个终止轮为终点，每一个轮可以带动多个齿轮，但一个齿轮只能被一个齿轮带动。求从驱动轮到终止轮每个轮的速度总和。

#### 解题分析： ####

这道题乍一看挺难得，但其实就是一个简单的搜索，将起点到终点所有权值的和加起来就行了。

#### AC代码： ####

#include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    
    #define N 1110
    
    struct edge{
        double x, y, r, w;
    }s[N];
    
    bool flag;
    int book[N], n;
    double tx, ty;
    
    bool judge(edge a, edge b)
    {
        double R = (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
        if(R == (a.r+b.r)*(a.r+b.r)) return true;
        return false;
    }
    
    void dfs(double sum, int k)
    {
        if(flag) return ;
        if(s[k].x == tx && s[k].y == ty){
            printf("%d\n", (int)sum);
            flag = true;
            return ;
        }
        for(int i = 0; i < n; i++){
            if(!book[i] && judge(s[i], s[k])){
                book[i] = 1;
                s[i].w = s[k].w*s[k].r/s[i].r;
                dfs(sum+s[i].w, i);
                book[i] = 0;
            }
        }
    }
    
    int main()
    {
        int T, i, j, k;
        scanf("%d", &T);
        while(T--){
            memset(book, 0, sizeof(book));
            scanf("%d%lf%lf", &n, &tx, &ty);
            for(i = 0; i < n; i++){
                s[i].w = 0;
                scanf("%lf%lf%lf", &s[i].x, &s[i].y, &s[i].r);
                if(!s[i].x && !s[i].y) j = i;
            }
            s[j].w = 10000;
            flag = false;
            book[j] = 1;
            dfs(10000, j);
        }
        return 0;
    }