题意:有两只青蛙,a在第一个石头,b在第二个石头,a要到b那里去,每种a到b的路径中都有最大边,求所有这些最大边的最小值。
思路:将所有边长存起来,排好序后,二分枚举答案。

  时间复杂度比较高,344ms。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h> using namespace std;
const int maxn=;
const int INF=0x3f3f3f3f;
double w[maxn][maxn]; //存储边长
double wlen[];
int con[maxn][maxn]; //con[i][j]=1表示i、j连通,con[i][j]=0表示不连通
int idx;
int n;
struct Node{
int x,y;
}node[maxn];
int main()
{
int t=,a,b;
double length;
int ans;
while(scanf("%d",&n)!=EOF){
if(n==)
break;
t++;
idx=;
memset(w,,sizeof(w));
printf("Scenario #%d\n",t);
for(int i=;i<n;i++){
scanf("%d%d",&a,&b);
node[i].x=a;
node[i].y=b;
}
for(int i=;i<n;i++){
for(int j=i+;j<n;j++){
//pow传递的参数先要强制转换成double,否则提交编译错误
length=pow(double(node[j].x-node[i].x),)+pow(double(node[j].y-node[i].y),);
length=sqrt(length);
w[i][j]=w[j][i]=length;
wlen[idx++]=length;
}
}
sort(wlen,wlen+idx);
//二分枚举所有可能的值,floyd的时候考虑所有长度不大于该值的边
int l=,r=idx-,mid;
while(l<=r){
mid=(l+r)>>;
for(int i=;i<n;i++){
for(int j=i+;j<n;j++){
//初始化,con[i][j]=1表示边i、j长度不大于枚举值,=0表示大于枚举值
if(w[i][j]>wlen[mid])
con[i][j]=con[j][i]=;
else
con[i][j]=con[j][i]=;
}
}
for(int k=;k<n;k++){
for(int i=;i<n;i++){
for(int j=;j<n;j++){
//只要有一对con[i][k]、con[k][j]连通,con[i][j]就连通
con[i][j]|=con[i][k]&con[k][j];
}
}
}
if(con[][]){
r=mid-;
ans=mid;
}
else{
l=mid+;
}
} printf("Frog Distance = %.3lf\n",wlen[ans]);
puts("");
}
return ;
}

这里附上别人的代码:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
double dist[][]; //dist[i][j]表示i到j的路径中边的最大值的最小值
int n;
struct Node {
int x;
int y;
} e[];
void Floyd() {
for(int k=; k<n; k++) {
for(int i=; i<n; i++) {
for(int j=; j<n; j++) {
if(max(dist[i][k],dist[k][j])<dist[i][j])
dist[i][j]=max(dist[i][k],dist[k][j]);
}
}
} }
int main() {
int t=;
while(~scanf("%d",&n)) {
if(n==)break;
for(int i=; i<n; i++) {
scanf("%d%d",&e[i].x,&e[i].y);
}
for(int i=; i<n; i++) {
for(int j=; j<n; j++) {
dist[i][j]=sqrt(pow((double)(e[i].x-e[j].x),)+pow((double)(e[i].y-e[j].y),));
}
}
Floyd();
printf("Scenario #%d\n",t++);
printf("Frog Distance = %.3f\n\n",dist[][]); }
}

最新文章

  1. react native中对props和state的理解
  2. lucence.net+盘古分词
  3. gulp详细入门教程-gulp demo download
  4. 类的继承和多态性-编写Java应用程序,定义Animal类,此类中有动物的属性:名称 name,腿的数量legs,统计动物的数量 count;方法:设置动物腿数量的方法 void setLegs(),获得腿数量的方法 getLegs(),设置动物名称的方法 setKind(),获得动物名称的方法 getKind(),获得动物数量的方法 getCount()。定义Fish类,是Animal类的子类,
  5. SQL判断字符串里不包含字母
  6. spark-submit常用参数
  7. LVM---动态调整磁盘容量
  8. CentOS 6破解Mysql5.5的办法
  9. Unity3D 集合插件目录
  10. PHP文件下载原理
  11. linux中压缩与解压缩命令小结
  12. html input type=&quot;button&quot; 页面跳转
  13. linux ps查看进程命令
  14. Java和PHP在Web开发方面的比较
  15. NET Core开发-读取配置文件Configuration
  16. U盘安装ubuntu14.10时出现的gfxboot.c32:not a COM32R image问题
  17. JTAG上有多个设备时,该如何接呢?
  18. python之读取配置文件模块configparser(二)参数详解
  19. Ubuntu 18.1远程登录服务器--ssh的安装
  20. CF 888E Maximum Subsequence

热门文章

  1. POJ 1285 确定比赛名次
  2. Java线程角度的内存模型和volatile型变量
  3. IE8浏览器跨域接口访问异常的解决办法
  4. 惠普M1005打印机无法自动进纸的问题
  5. Silverlight动画的基本知识、关键帧动画
  6. [大牛翻译系列]Hadoop(10)MapReduce 性能调优:诊断reduce性能瓶颈
  7. php多层数组与对象的转换实例代码
  8. mysql时间处理
  9. rtx信息泄漏利结合弱口令导致被批量社工思路
  10. 【转】char*,const char*和string的相互转换