13051: 航空公司发表时间:2022-10-28 23:17 13051: 航空公司时间限制: 1 Sec 内存限制: 128 MB 题目描述A国是一个拥有很多岛屿的国家。岛屿上的风景迷人且各有特点。不但如此,这些岛屿都是圆形的。所有的一切吸引了很多国内外的游客,A国当然不会放弃这个发展经济的好机会了。为了更好发展旅游业,A国决定由S航空公司来设计生产用于往返于各个岛屿之间的旅游小型机。 输入第一行:一个整数N (1<N<=1000) 输出输出一个整数V (V是保证可以往返于任意两个岛屿之间的旅游小型机的最小油箱容积)。 样例输入 Copy3 0 0 1 3 0 1 0 4 1 样例输出 Copy2 提示输入样例中A岛位于(0,0),半径为1;B岛位于(3,0),半径为1;C岛位于(0,4),半径为1.从A岛到达B岛的最近距离需要1个单位的汽油。从A岛到达C岛的最近距离需要2个单位的汽油。直接从B岛到达C岛需要3个单位的汽油,也就是说需要3个单位大小的油箱。但是,假如先从B岛飞到A岛,然后再从A岛飞到C岛,那么就只需要一个2个单位大小的油箱。所以,样例的正确输出应当是2。 很典型的最小生成树问题。如果要学习最小生成树的算法,详情见前面的文章。 这里只是边权值需要简单处理,减去岛的边长。 #include<bits/stdc++.h> using namespace std; struct Node{ int x,y,dis; }a[1000005]; int read(){ char c=getchar();int f=0,ans=0; while(!isdigit(c)){if(c=='-')f=1;c=getchar();} while(isdigit(c)){ans=ans*10+c-'0';c=getchar();} return f?-ans:ans; } int pf(int x){ return x*x; } bool cmp(Node x,Node y){return x.dis<y.dis;} int fa[1005]; int find_fa(int x){return x!=fa[x]?fa[x]=find_fa(fa[x]):x;} int main(){ int n; int x[1005],y[1005],r[1005]; n=read(); for(int i=1;i<=n;i++){ x[i]=read();y[i]=read();r[i]=read(); } int tot=0; for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++){ a[++tot].x=i;a[tot].y=j; double len=pf(x[i]-x[j])+pf(y[i]-y[j]); len=sqrt(len); a[tot].dis=ceil(len)-r[i]-r[j]; } sort(a+1,a+1+tot,cmp); for(int i=1;i<=n;i++) fa[i]=i; int ans=-1; for(int i=1;i<=tot;i++){ int fx=find_fa(a[i].x),fy=find_fa(a[i].y); if(fx!=fy){ans=a[i].dis;fa[fx]=fy;} } cout<<ans<<endl; return 0; } |