题目链接:http://nyoj.top/problem/1276

  • 内存限制:64MB 时间限制:1000ms

题目描述

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

解题思路

BFS搜索，每次找寻与其相切的圆。最后要注意，输出整数部分不是保留0位小数。

#include <bits/stdc++.h>
using namespace std;
struct edge {
    int x, y, r;
    double st, vt;
}e[1105], s, p, q;
int vis[1105], n, xt, yt;
bool Judge(edge a, edge b) {
    if ((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) != (a.r + b.r) * (a.r + b.r))
        return false;
    return true;
}
double BFS() {
    s.st = 10000;
    s.vt = 10000;
    queue <edge> Q;
    Q.push(s);
    while (!Q.empty()) {
        p = Q.front();
        Q.pop();
        for (int i = 0; i < n; i++) {
            if (!vis[i] && Judge(p, e[i])) {
                q = e[i];
                q.vt = p.vt * p.r / e[i].r;
                q.st = p.st + q.vt; 
                Q.push(q);
                if (!(q.x - xt) && !(q.y - yt))
                    return q.st;
                vis[i] = 1;
            }
        }
    }
    return 0;
}
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        memset(vis, 0, sizeof(vis));
        scanf("%d%d%d", &n, &xt, &yt);
        for (int i = 0; i < n; i++) {
            scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].r);
            if (!e[i].x && !e[i].y) {
                s.r = e[i].r;
                s.x = s.y = 0;
                vis[i] = 1;
            }
        }
        printf("%lld\n", (long long)BFS());
    }
    return 0;
}