题解 P2903 【[USACO08MAR]麻烦的干草打包机The Loathesome Hay Baler】

· · 题解

这个题数据范围N<=1050 ， O(N²)的BFS，每次逐个计算两个齿轮的距离 ，实现过程很容易。

具体细节见代码注释。

P.S. 齿轮转的方向和结果好像没什么关系，于是我算的时候就没取相反数。

//Bzoj1615 麻烦的干草打包机
#include<bits/stdc++.h>
#define MAXN 1084
struct cycle{
    int x,y,r;
}a[MAXN];
using namespace std;
int N,xt,yt,st,ed,p[MAXN];
double s[MAXN],ans;
bool vis[MAXN];
void BFS()
{
    queue<int>q;    
    vis[st]=1,s[st]=10000;                    //初值
    q.push(st);
    while(!q.empty())
    {
        int tmp=q.front();q.pop();
        for(int i=1;i<=N;i++)
        {
            if(vis[i])continue;
            if((a[tmp].x-a[i].x)*(a[tmp].x-a[i].x)+(a[tmp].y-a[i].y)*(a[tmp].y-a[i].y)==(a[i].r+a[tmp].r)*(a[i].r+a[tmp].r))
            {                                 //上面这行是判断  距离的平方 是否等于 两齿轮半径和的平方         
                vis[i]=1;
                double t=a[tmp].r*1.0/a[i].r;                //计算
                s[i]=s[tmp]*t; 
                p[i]=tmp;                                                         //这里说一下这个p数组是记路径用的，方便加和。
                if(i==ed)return ;                                              //跳出
                q.push(i);
            } 
        }
    }
}
int main()
{
    scanf("%d%d%d",&N,&xt,&yt);
    for(int i=1;i<=N;i++){
        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].r);
        if(a[i].x==0&&a[i].y==0)st=i;
        if(a[i].x==xt&&a[i].y==yt)ed=i;    //存一下开始和结尾的位置
    }
    BFS();
    for(int i=ed;i;i=p[i])
        ans+=s[i];
    printf("%d",(int)ans);                               //这个地方要取整，四舍五入会WA30
    return 0;
} 
博客链接http://www.cnblogs.com/Elfish/p/7634159.html