描述
http://www.lydsy.com/JudgeOnline/problem.php?id=1615
一个主动轮带着一些*转,*带着*转,*带着*转...一个非主动轮只会被一个*带着转.求从主动轮到某一个*的路上所有*的转速的绝对值之和.
分析
从起点开始,枚举相接触的*,只要不是之前路上的(带着当前*转的)*,就继续往下走.宽搜深搜都可以.
注意:
1.%.0lf是会四舍五入的!所以要强制转化成int.
宽搜:
#include <bits/stdc++.h>
using namespace std; const int maxn=+;
const double eps=1e-;
struct node{ double x,y,r; }a[maxn];
int n,s,t;
int q[maxn];
bool vis[maxn];
double xt,yt;
double s_[maxn],ans[maxn];
inline bool c(node a,node b){ return fabs((sqrt(pow(a.x-b.x,)+pow(a.y-b.y,))-a.r-b.r))<eps; }
int main(){
scanf("%d%lf%lf",&n,&xt,&yt);
for(int i=;i<=n;i++){
scanf("%lf%lf%lf",&a[i].x,&a[i].y,&a[i].r);
if(a[i].x==0.0&&a[i].y==0.0) s=i;
else if(a[i].x==xt&&a[i].y==yt) t=i;
}
int front=,tail=;
q[tail++]=s; vis[s]=true; s_[s]=ans[s]=;
while(front!=tail){
int u=q[front++];
if(u==t){ printf("%d\n",(int)ans[u]); return ; }
for(int v=;v<=n;v++)if(!vis[v]&&c(a[u],a[v])){
s_[v]=-s_[u]*a[u].r/a[v].r;
ans[v]+=fabs(s_[v])+ans[u];
vis[v]=true;
q[tail++]=v;
}
}
return ;
}
深搜:
#include <bits/stdc++.h>
using namespace std; const int maxn=+;
const double eps=1e-;
struct node{ double x,y,r; }a[maxn];
int n,s,t;
int q[maxn];
double xt,yt;
bool vis[maxn];
inline bool c(node a,node b){ return fabs(sqrt(pow(a.x-b.x,)+pow(a.y-b.y,))-a.r-b.r)<eps; }
double dfs(int u,double sp,double ans){
if(u==t) return ans;
for(int v=;v<=n;v++)if(!vis[v]&&c(a[u],a[v])){
vis[v]=true;
double S=-sp*a[u].r/a[v].r;
return dfs(v,S,ans+fabs(S));
}
}
int main(){
scanf("%d%lf%lf",&n,&xt,&yt);
for(int i=;i<=n;i++){
scanf("%lf%lf%lf",&a[i].x,&a[i].y,&a[i].r);
if(a[i].x==0.0&&a[i].y==0.0) s=i;
else if(a[i].x==xt&&a[i].y==yt) t=i;
}
vis[s]=true;
printf("%d\n",(int)dfs(s,,));
return ;
}