POJ2728 无向图中对每条边i 有两个权值wi 和vi 求一个生成树使得 (w1+w2+...wn-1)/(v1+v2+...+vn-1)最小。

采用二分答案mid的思想。

将边的权值改为 wi-vi*mid.

对所有边求和后除以v 即为 (w1+w2+...wn-1)/(v1+v2+...+vn-1)-mid. 因此,若当前生成树的权值和为0,就找到了答案。否则更改二分上下界。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std; const int maxn=1000;
int n;
double lenth[maxn],nowans,lef,righ,w[maxn][maxn],v[maxn][maxn];
bool intree[maxn]; double ab(double x)
{
if(x>0)return x;
else return x*(-1);
} class point
{
public:
double x;double y;double z;
}; point po[maxn]; double dist(point a,point b); double cost(point a,point b)
{
return ab((a.z-b.z));
} class edge
{
public:
int pa;int pb;
double dis;double cos;double div;
edge(int a,int b,double(*distance)(point,point),double (*cost)(point,point))
{
this->pa=a;this->pb=b;
this->dis=distance(po[a],po[b]);
this->cos=cost(po[a],po[b]);
this->div=cos/dis;
}
bool operator <(const edge b)const
{
return (this->cos-(this->dis*nowans))>(b.cos-(b.dis*nowans));//这个算法的核心
}
}; double dist(point a,point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
} double min(double a,double b)
{
if(a<b)return a;
else return b;
} int main()
{
ios::sync_with_stdio(false);
while(cin>>n)
{
if(n==0)return 0;
lef=0.0;righ=1e6;
for(int i=0;i<n;i++)
{
cin>>po[i].x>>po[i].y>>po[i].z;
}
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
w[i][j]=cost(po[i],po[j]);
v[i][j]=dist(po[i],po[j]);
}
double minnow;
while(true)
{
nowans=(lef+righ)/2;minnow=0;
memset(intree,0,sizeof(intree));
for(int i=1;i<n;i++)
{
lenth[i]=w[0][i]-v[0][i]*nowans;
}
lenth[0]=0.0;intree[0]=true;
for(int i=1;i<n;i++)
{
double temp=1e+30;int tj=0;
for(int j=1;j<n;j++)
if(!intree[j]&&lenth[j]<temp)
{
tj=j;
temp=lenth[j];
}
minnow+=lenth[tj];
intree[tj]=true;
for(int j=1;j<n;j++)
{
if(!intree[j])lenth[j]=min(lenth[j],w[tj][j]-v[tj][j]*nowans);
}
}
if(ab(minnow-0.0)<1e-5)break;
if(minnow>0)lef=nowans;
else righ=nowans;
}
printf("%.3lf\n",(lef+righ)/2);
}
return 0;
}

  用二分答案思想解决的生成树问题还有单度限制最小生成树,参考CODEFORCES 125E.

最新文章

  1. bootstrap基本模板
  2. Windbg跟踪临界区的BUG
  3. ArcMap常用VBA
  4. Web 开发中应用 HTML5 技术的10个实例教程
  5. java notify和notifyAll的区别
  6. 左倾堆(二)之 C++的实现
  7. compare:(字符串的大小比较)
  8. vim开发环境配置
  9. span标签里的内容在IE下显示,而在谷歌浏览器下不显示
  10. OpenGL5-纹理贴图
  11. js常用函数(不断添加中。。。)
  12. node http.request请求
  13. Linux-2.6.32内核编译流量计数器nfacct
  14. Maven搭建struts2+spring+hibernate环境
  15. BZOJ 3652: 大新闻(数位DP+概率论)
  16. 用Python解答百度测试开发算法面试题
  17. centos7.4下Jira6环境部署及破解操作记录(完整版)
  18. 在eclipse中, 如何快速输入(快捷键)System.out.println();
  19. 强制DataNode向NameNode上报blocks
  20. eclipse 断点找到同名的其它类

热门文章

  1. stark组件之显示页面搭建(四)
  2. 圆角计算 Shader
  3. 【01染色法判断二分匹配+匈牙利算法求最大匹配】HDU The Accomodation of Students
  4. [cf360 div1.C]The Values You Can Make[Dp]
  5. 删除右键open foler as pycharm project(WIN10)
  6. JQuery判断radio是否选中并获取选中值的示例代码
  7. kibana启动--nohup在关闭终端后无效&amp;&amp;守护进程详解
  8. nyoj_176_整数划分(二)_201404261715
  9. docker容器-快速部署Jenkins
  10. seajs入门使用