# 描述

http://www.lydsy.com/JudgeOnline/problem.php?id=1615

# 分析

1.%.0lf是会四舍五入的!所以要强制转化成int.

``` 1 #include <bits/stdc++.h>
2 using namespace std;
3
4 const int maxn=1050+5;
5 const double eps=1e-10;
6 struct node{ double x,y,r; }a[maxn];
7 int n,s,t;
8 int q[maxn];
9 bool vis[maxn];
10 double xt,yt;
11 double s_[maxn],ans[maxn];
12 inline bool c(node a,node b){ return fabs((sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2))-a.r-b.r))<eps; }
13 int main(){
14     scanf("%d%lf%lf",&n,&xt,&yt);
15     for(int i=1;i<=n;i++){
16         scanf("%lf%lf%lf",&a[i].x,&a[i].y,&a[i].r);
17         if(a[i].x==0.0&&a[i].y==0.0) s=i;
18         else if(a[i].x==xt&&a[i].y==yt) t=i;
19     }
20     int front=0,tail=0;
21     q[tail++]=s; vis[s]=true;  s_[s]=ans[s]=10000;
22     while(front!=tail){
23         int u=q[front++];
24         if(u==t){ printf("%d\n",(int)ans[u]); return 0; }
25         for(int v=1;v<=n;v++)if(!vis[v]&&c(a[u],a[v])){
26             s_[v]=-s_[u]*a[u].r/a[v].r;
27             ans[v]+=fabs(s_[v])+ans[u];
28             vis[v]=true;
29             q[tail++]=v;
30         }
31     }
32     return 0;
33 }```

``` 1 #include <bits/stdc++.h>
2 using namespace std;
3
4 const int maxn=1050+5;
5 const double eps=1e-8;
6 struct node{ double x,y,r; }a[maxn];
7 int n,s,t;
8 int q[maxn];
9 double xt,yt;
10 bool vis[maxn];
11 inline bool c(node a,node b){ return fabs(sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2))-a.r-b.r)<eps; }
12 double dfs(int u,double sp,double ans){
13     if(u==t) return ans;
14     for(int v=1;v<=n;v++)if(!vis[v]&&c(a[u],a[v])){
15         vis[v]=true;
16         double S=-sp*a[u].r/a[v].r;
17         return dfs(v,S,ans+fabs(S));
18     }
19 }
20 int main(){
21     scanf("%d%lf%lf",&n,&xt,&yt);
22     for(int i=1;i<=n;i++){
23         scanf("%lf%lf%lf",&a[i].x,&a[i].y,&a[i].r);
24         if(a[i].x==0.0&&a[i].y==0.0) s=i;
25         else if(a[i].x==xt&&a[i].y==yt) t=i;
26     }
27     vis[s]=true;
28     printf("%d\n",(int)dfs(s,10000,10000));
29     return 0;
30 }```

## 1615: [Usaco2008 Mar]The Loathesome Hay Baler麻烦的干草打包机

1615: [Usaco2008 Mar]The Loathesome Hay Baler麻烦的干草打包机 Time Limit: 5 Sec  Memory Limit: 64 MBSubmit: 574  Solved: 226[Submit][Status] Description Farmer John新买的干草打包机的内部结构大概算世界上最混乱的了,它不象普通的机器一样有明确的内部传动装置,而是,N (2 <= N <= 1050)个齿轮互相作用,每个齿轮都可能驱动着多个齿轮. FJ

## 洛谷P2903 [USACO08MAR]麻烦的干草打包机The Loathesome Hay Baler

P2903 [USACO08MAR]麻烦的干草打包机The Loathesome Hay Baler 题目描述 Farmer John has purchased the world's most loathesome hay baler. Instead of having a drive-roller that drives maybe an idler roller that drives the power take-off for the baler, it has N rollers

## 大神刷题表

9月27日 后缀数组:[wikioi3160]最长公共子串 dp:NOIP2001统计单词个数 后缀自动机:[spoj1812]Longest Common Substring II [wikioi3160]最长公共子串 [spoj7258]Lexicographical Substring Search 扫描线+set:[poj2932]Coneology 扫描线+set+树上删边游戏:[FJOI2013]圆形游戏 结论:[bzoj3706][FJ2014集训]反色刷 最小环:[poj1734

## 区间调度问题

1. 相关定义 在数学里,区间通常是指这样的一类实数集合:如果x和y是两个在集合里的数,那么,任何x和y之间的数也属于该集合.区间有开闭之分,例如(1,2)和[1,2]的表示范围不同,后者包含整数1和2. 在程序世界,区间的概念和数学里没有区别,但是往往有具体的含义,例如时间区间,工资区间或者音乐中音符的开始结束区间等,图一给出了一个时间区间的例子.区间有了具体的含义之后,开闭的概念就显得非常重要,例如时间区间[8:30,9:30]和[9:30,10:30]两个区间是有重叠的,但是[8:30,9