BZOJ_1615_[Usaco2008_Mar]_The Loathesome_Hay Baler_麻烦的干草打包机_(模拟+宽搜/深搜)

描述



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 }

时间: 06-11

BZOJ_1615_[Usaco2008_Mar]_The Loathesome_Hay Baler_麻烦的干草打包机_(模拟+宽搜/深搜)的相关文章

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

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

感觉自己像个智障 直接bfs 然而读入没判负号查了半小时.. 1 #include<cstdio> 2 #include<cctype> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 using namespace std; 7 #define maxn 1100 8 #define eps 1e-8 9 int n,tx,ty; 10 int st,ed; 11 in

9月刷题总结

全是usaco水题.... 贪心(这个要放在首位,思想太重要): [BZOJ]1650: [Usaco2006 Dec]River Hopscotch 跳石子(二分+贪心) [BZOJ]1691: [Usaco2007 Dec]挑剔的美食家(multiset+贪心) [BZOJ]1692 & 1640: [Usaco2007 Dec]队列变换(后缀数组+贪心) [BZOJ]1620: [Usaco2008 Nov]Time Management 时间管理(贪心) [BZOJ]1634: [Usa

大神刷题表

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

usaco silver

大神们都在刷usaco,我也来水一水 1606: [Usaco2008 Dec]Hay For Sale 购买干草   裸背包 1607: [Usaco2008 Dec]Patting Heads 轻拍牛头 神转化,筛法 1609: [Usaco2008 Feb]Eating Together麻烦的聚餐  LIS 1610: [Usaco2008 Feb]Line连线游戏 sb题 1611: [Usaco2008 Feb]Meteor Shower流星雨  BFS 1612: [Usaco200

acm常见算法及例题

转自:http://blog.csdn.net/hengjie2009/article/details/7540135 acm常见算法及例题 初期:一.基本算法:     (1)枚举. (poj1753,poj2965)     (2)贪心(poj1328,poj2109,poj2586)     (3)递归和分治法.     (4)递推.     (5)构造法.(poj3295)     (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996)二.图算法

区间调度问题

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

为猿七年有余,痒否?痛否?

还未有感,已然岁末,犹叹时之箭逝去如斯也,稍纵命再减一.回首望,为猿七年有余已,虽不成气候,亦未全蹉跎.略做小结,以不惘逝去之时日,亦会大益于尔后路途.若博文能助足下之一二,孤将甚悦. 职业是无数个连接起来的马拉松 小学时,我们很清楚的知道5年后就毕业了(孤当年是五四制,现在貌似有的地方也是),无论多么讨厌老师或者 同学,或者学校,都知道最多忍5年就结束了:初中高中也一样,三四年样子,很快就过去了,多少欢乐悲喜都会很快的过去:大学更是如此,从入学进校园那天起你就开始倒计时,知道四年后的一天要离开