P2903 [USACO08MAR]麻烦的干草打包机The Loathesome Hay Baler
题目问的是从出发点一直跑到终点的一条链上所有齿轮的速度和
其他的不用考虑
直接搜就好了
注意求的是绝对值之和，不是和的绝对值，所以不用考虑方向问题
注意 N<=1050 数组不要只开1007！
代码简单不注释
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=3007; int n,st,ed; int pos[N][2],r[N]; double ans; inline double f(int a,int b) { double x=pos[a][0]-pos[b][0],y=pos[a][1]-pos[b][1]; return sqrt(x*x+y*y); } int fir[N],from[N<<1],to[N<<1],cnt; inline void add(int &a,int &b) { from[++cnt]=fir[a]; fir[a]=cnt; to[cnt]=b; } bool vis[N]; void dfs(int x,double res,double v) { if(x==ed) { ans=res; return; } vis[x]=1; for(int i=fir[x];i;i=from[i]) { int &u=to[i]; if(vis[u]) continue; double vv=v*(double)r[x]/(double)r[u]; dfs(u,res+vv,vv); } } int main() { n=read(); pos[0][0]=read(); pos[0][1]=read(); for(int i=1;i<=n;i++) { pos[i][0]=read(),pos[i][1]=read(),r[i]=read(); if(pos[i][0]==0&&pos[i][1]==0) st=i; if(pos[i][0]==pos[0][0]&&pos[i][1]==pos[0][1]) ed=i; } for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) if(f(i,j)==(double)r[i]+(double)r[j]) add(i,j),add(j,i); dfs(st,10000.0,10000.0); printf("%d",(int)ans); return 0; }