首页 > 代码库 > 机械设备--第九届省赛--深搜
机械设备--第九届省赛--深搜
-
Alpha 公司设计出一种节能的机器设备。它的内部结构是由 N 个齿轮组成。整个机器设备有 一个驱动齿轮,当启动它时,它立即按 10,000 圈/小时转速顺时针转动,然后它又带动与它相切 的齿轮反方向,即逆时针转动。齿轮之间互相作用,每个齿轮都可能驱动着多个齿轮,最终带动 一个工作齿轮完成相应的任务。 在这套设备中,记录了每个齿轮的圆心坐标和齿轮半径。已知驱动齿轮位于(0,0),最终的 工作齿轮位于(Xt, Yt)。 Alpha 公司想知道传动序列中所有齿轮的转速。所谓传动序列,即能量由驱动齿轮传送,最 后到达工作齿轮的过程中用到的所有齿轮。能量传送过程是,在一个半径为 R,转速为 S 圈/每小 时的齿轮的带动下,与它相切的半径为 R’的齿轮的转速为-S*R/R’ 转/小时。负号的意思是, 表 示按反方向转动。
已知,机器设备中除了驱动齿轮以外,所有齿轮都可能被另外某个齿轮带动,并且不会出现 2 个不同的齿轮带动同一个齿轮的情况。 你的任务是计算整个传动序列中所有齿轮的能量之和。即所有齿轮转速的绝对值之和。
- 输入
- 第一行: T 表示以下有 T 组测试数据(1≤T ≤8)
对每组测试数据:
第 1 行: N Xt Yt (2≤N ≤1100)
接下来有 N 行, Xi Yi Ri 表示 N 个齿轮的坐标和半径 i=1,2,….,N
( -5000 ≤Xi ,Yi ≤ 5000 3 ≤ Ri ≤ 1000 )
坐标以及半径是整数
- 输出
- 每组测试数据,输出占一行,即所有齿轮转速的绝对值之和 在double范围内,输出整数部分
- 样例输入
-
1 4 32 54 0 30 20 0 0 10 32 54 20 -40 30 20
- 样例输出
-
20000
题意求出连接起点圆到终点圆的所有齿轮转速和
废话不多说,深搜,广搜都行,以下深搜代码
#include <stdio.h> #include <algorithm> #include<string.h> using namespace std; const int N = 1118; int xi, n, yi, book[N], x[N], y[N], f, R[N]; double sum; void dfs(int xx, int yy, int r, double sp) { if(f==1) return;///剪枝 for(int i=1; i<=n; i++) { if(xx==xi&&yy==yi) { printf("%d\n",(int)sum);///这个题比较坑的一点只取整数部分 f=1; return; } if(((x[i]-xx)*(x[i]-xx)+(y[i]-yy)*(y[i]-yy)==(r+R[i])*(r+R[i])) && book[i]==0) { sum+=(sp*1.0*r)/(1.0*R[i]); book[i]=1; dfs(x[i], y[i], R[i], (sp*r*1.0)/R[i]); book[i]=0; sum-=(sp*1.0*r)/(R[i]*1.0);///回溯 } } } int main() { int T, t; scanf("%d", &T); while(T--) { scanf("%d%d%d", &n, &xi, &yi); for(int i=1; i<=n; i++) { scanf("%d%d%d", &x[i], &y[i], &R[i]); if(x[i]==0&&y[i]==0) t=i;///记录起点 } memset(book, 0, sizeof(book)); sum=10000.0; book[t]=1; f=0; dfs(0, 0, R[t], 10000.0); } return 0; }
机械设备--第九届省赛--深搜
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。