[搜索]USACO Mar08 麻煩的乾草打包機 baler 解題報告

【問題描述】
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個不同的齒輪帶動同一個齒輪的情況。

相信你能輕易地寫個程序來完成這些計算

程序名: baler

輸入格式:

第1行: 3個用空格隔開的整數：N，X_t，Y_t

第2..N+1行: 第i+1描述了齒輪i的位置及半徑：X_i，Y_i，以及R_i

輸入樣例 (baler.in):

4 32 54

0 0 10

0 30 20

32 54 20

-40 30 20

輸入說明:

機器裏一共有4個齒輪，位於0,0的是半徑爲10的驅動齒輪，它帶動了位於0,30的，半徑爲20的某個齒輪。這個齒輪又間接帶動了位於32,54，半徑爲20的工作齒輪，以及一個位於-40,30，半徑同樣爲20的冗餘的齒輪。

輸出格式:

第1行: 輸出所有在傳動中起到作用的齒輪轉速的絕對值，包括驅動齒輪和工作齒輪。只需要輸出的整數部分，與答案相差不超過1即可。

輸出樣例 (baler.out):

20000

輸出說明:

齒輪 位置 半徑 轉速

1 (0,0) 10 10,000

2 (0,30) 20 -5,000

3 (32,54) 20 5,000

------

齒輪轉速絕對值之和:20,000

【分析】

這是一顆樹，對於樹，不需要求最短路，只需要一邊廣度優先搜索即可。

注意：1) 中心位於(0,0)的輪子不一定是第一個

          2)程序中多數變量是double 型

          3)輪子轉速的計算

          4)兩圓相切的公式就是勾股定理的平方和公式

【我的代碼】

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cmath>
using namespace std;

class ROLLER
{
public:
    int x;
    int y;
    int r;
    double s;
}Roller[1051];
int N;
int X,Y;
int ENum;
int SNum;

long long squre(int a)
{
    long long tmp=a*a;
    return tmp;
}

void init()
{
    scanf("%d %d %d\n",&N,&X,&Y);
    for (int i=1;i<=N;i++)
    {
        scanf("%d %d %d\n",&Roller[i].x,&Roller[i].y,&Roller[i].r);
   
        if(Roller[i].x==0 && Roller[i].y==0)
            SNum=i;
       
        if(Roller[i].x==X && Roller[i].y==Y)
            ENum=i;
    }
    Roller[SNum].s=10000;
}


class QUEUE
{
public:
    double S;//當前輪子轉速
    int C;//當前輪子的編號
    bool Rol[1051];
    QUEUE()
    {
        for (int i=1;i<=1050;i++)
            Rol[i]=true;
    }
}Q[1200];


double GetSpeed(double ss,int rd,int rx)
{
    double rrd=(double)(rd);
    double rrx=(double)(rx);
    double res=-ss*rrd/rrx;
    return res;
}

double absd(double aa)
{
    if(aa>=0)
        return aa;
    else
        return -aa;
}
   

int bfs()
{
    int Big=1;
    int Small=0;
    Q[0].Rol[SNum]=false;
    Q[0].C=SNum;
    Q[0].S=10000;
   
    int Tn,Tx,Ty,Tr;
    double Ts;
    int Nx,Ny,Nr;
    long long ta,tb,tc;
    while(Small<=Big)
    {
        Tn=Q[Small].C;
        Tx=Roller[Tn].x;
        Ty=Roller[Tn].y;
        Tr=Roller[Tn].r;
        Ts=Q[Small].S;
       
        for (int i=1;i<=N;i++)
        {
            if(i==Tn)
                continue;
           
            if(!Q[Small].Rol[i])
                continue;
           
            Nx=Roller[i].x;
            Ny=Roller[i].y;
            Nr=Roller[i].r;
           
            ta=squre(Nx-Tx);
            tb=squre(Ny-Ty);
            tc=squre(Nr+Tr);
           
            if( ta+tb!=tc )
                continue;
           
            for (int k=1;k<=N;k++)
                Q[Big].Rol[k]=Q[Small].Rol[k];
            Q[Big].C=i;
            Q[Big].S=GetSpeed(Ts,Tr,Nr);
            Q[Big].Rol[i]=false;
            Roller[i].s=Q[Big].S;
            if(i==ENum)
                return Big;
           
            Big++;
        }
       
        Small++;
    }
    return Big;
}

int main()
{
    freopen("baler.in","r",stdin);
    freopen("baler.out","w",stdout);
    init();
    int EQ=bfs();
    double Tot=0;
    for (int i=1;i<=N;i++)
    {
        if(!Q[EQ].Rol[i])
            Tot=Tot+absd(Roller[i].s);
    }
    cout<<(int)(Tot)<<endl;
    return 0;
}