【BZOJ1615】[Usaco2008 Mar]The Loathesome Hay Baler 麻烦的干草打包机

2014-06-01
竞赛题解 / 搜索
BFSBZOJUSACO

描述 Description

Farmer John 新买的干草打包机的内部结构大概算世界上最混乱的了，它不象普通的机器一样有明确的内部传动装置，而是，N (2 <= N <= 1050) 个齿轮互相作用，每个齿轮都可能驱动着多个齿轮。 FJ 记录了对于每个齿轮 i，记录了它的 3 个参数：X_i，Y_i 表示齿轮中心的位置坐标 (-5000 <= X_i <= 5000; -5000 <= Y_i <= 5000)；R_i 表示该齿轮的半径 (3 <= R_i <= 800)。驱动齿轮的位置为 0,0，并且 FJ 也知道最终的工作齿轮位于 X_t,Y_t。 驱动齿轮顺时针转动，转速为 10,000 转 / 小时。你的任务是，确定传动序列中所有齿轮的转速。传动序列的定义为，能量由驱动齿轮传送到工作齿轮的过程中用到的所有齿轮的集合。对能量传送无意义的齿轮都应当被忽略。在一个半径为 Rd，转速为 S 转 / 每小时的齿轮的带动下，与它相接的半径为 Rx 的齿轮的转速将为 - S*Rd/Rx 转 / 小时。S 前的负号的意思是，一个齿轮带动的另一个齿轮的转向会与它的转向相反。 FJ 只对整个传动序列中所有齿轮速度的绝对值之和感兴趣，你的任务也就相应转化成求这个值。机器中除了驱动齿轮以外的所有齿轮都被另外某个齿轮带动，并且不会出现 2 个不同的齿轮带动同一个齿轮的情况。 相信你能轻易地写个程序来完成这些计算:)

描述了齿轮 i 的位置及半径：X_i，Y_i，以及 R_i

输出格式 OutputFormat

第 1 行: 输出所有在传动中起到作用的齿轮转速的绝对值，包括驱动齿轮和 工作齿轮。只需要输出答案的整数部分.

样例输入 SampleInput

11 345 87
159 212 80
0 -120 95
23 314 30
345 87 53
96 -48 25
0 0 25
261 -48 106
63 84 80
138 -48 17
-25 350 30
71 278 30

样例输出 SampleOutput

44412

数据范围和注释 Hint

机器里一共有 4 个齿轮，位于 0,0 的是半径为 10 的驱动齿轮，它带动了位于 0,30 的，半径为 20 的某个齿轮。这个齿轮又间接带动了位于 32,54，半径为 20 的工作齿轮，以及一个位于 - 40,30，半径同样为 20 的冗余的齿轮。

来源 Source

Silver

BZOJ 1615

代码 Code

除了驱动齿轮外每个齿轮都只会与至多两个齿轮接触，bfs 或 dfs 均可。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
struct point
{
    double z,y,x;
}a[1100];
struct que
{
    int s,fa;
    double rou;
}f[500000];
int c[1100][5];
int b[1100];
int i,j,t,n,m,l,r,k;
double ex,ey;
inline double dis(point a,point b)
{
    return (sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)));
}
void output(int m)
{
    int i,j;
    double t=0;
    for (i=m;i!=-1;i=f[i].fa) t+=fabs(f[i].rou);
    printf("%d\n",(int)t);
}
int main()
{
    scanf("%d%lf%lf",&n,&ex,&ey);
    for (i=1;i<=n;i++)
    {
        scanf("%lf%lf%lf",&a[i].x,&a[i].y,&a[i].z);
        if (a[i].x==0 && a[i].y==0) t=i;
    }
    for (i=1;i<=n;i++) for (j=1;j<=n;j++)
    {
        if (dis(a[i],a[j])==a[i].z+a[j].z) c[i][++c[i][0]]=j;
    }
    memset(b,0,sizeof(b));
    l=0;r=l;f[l].s=t;f[l].fa=-1;f[l].rou=10000;b[t]=true;
    while (r>=l)
    {
        t=f[l].s;
        for (i=1;i<=c[t][0];i++) if (b[c[t][i]]==false)
        {
            b[c[t][i]]=true;
            f[++r].s=c[t][i];f[r].fa=l;f[r].rou=-((double)f[l].rou*a[t].z/a[c[t][i]].z);
            if (a[f[r].s].x==ex && a[f[r].s].y==ey)
            {
                output(r);
                return 0;
            }
        }
        b[t]=false;
        l++;
    }
    return 0;
}