POJ——T 2728 Desert King
http://poj.org/problem?id=2728
Time Limit: 3000MS | Memory Limit: 65536K | |
Total Submissions: 27191 | Accepted: 7557 |
Description
After days of study, he finally figured his plan out. He wanted the average cost of each mile of the channels to be minimized. In other words, the ratio of the overall cost of the channels to the total length must be minimized. He just needs to build the necessary channels to bring water to all the villages, which means there will be only one way to connect each village to the capital.
His engineers surveyed the country and recorded the position and altitude of each village. All the channels must go straight between two villages and be built horizontally. Since every two villages are at different altitudes, they concluded that each channel between two villages needed a vertical water lifter, which can lift water up or let water flow down. The length of the channel is the horizontal distance between the two villages. The cost of the channel is the height of the lifter. You should notice that each village is at a different altitude, and different channels can't share a lifter. Channels can intersect safely and no three villages are on the same line.
As King David's prime scientist and programmer, you are asked to find out the best solution to build the channels.
Input
Output
Sample Input
4
0 0 0
0 1 1
1 1 2
1 0 3
0
Sample Output
1.000
Source
#include <algorithm>
#include <cstdio>
#include <cmath> #define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b) inline void read(int &x)
{
x=; register char ch=getchar();
for(; ch>''||ch<''; ) ch=getchar();
for(; ch>=''&&ch<=''; ch=getchar()) x=x*+ch-'';
} const double eps(1e-);
const int N();
struct Node {
int x,y,h;
}city[N];
int n; double L,R,Mid,ans;
struct Edge {
int u,v;
double w;
Edge(int u=,int v=,double w=0.0):u(u),v(v),w(w){}
bool operator < (const Edge&x)const { return w<x.w; }
}road[N*N]; inline double Dis(Node a,Node b)
{
double x=1.0*(a.x-b.x)*(a.x-b.x);
double y=1.0*(a.y-b.y)*(a.y-b.y);
return abs(a.h-b.h)-Mid*sqrt(x+y);
} int fa[N];
int find(int x) { return x==fa[x]?x:fa[x]=find(fa[x]); } inline bool check()
{
double ret=; int cnt=,m=;
for(int i=; i<=n; fa[i]=i++)
for(int j=; j<=n; ++j)
if(i!=j) road[++m]=Edge(i,j,Dis(city[i],city[j]));
std::sort(road+,road+m+);
for(int fx,fy,i=; i<=m; ++i)
{
fx=find(road[i].u),
fy=find(road[i].v);
if(fx==fy) continue;
fa[fx]=fy; ret+=road[i].w;
if(++cnt==n-) return ret<;
}
} int Presist()
{
for(; scanf("%d",&n)&&n; )
{
for(int i=; i<=n; ++i)
{
read(city[i].x),
read(city[i].y),
read(city[i].h),
R=max(R,1.0*city[i].h);
}
for(L=; L+eps<R; )
{
Mid=(L+R)/2.0;
if(check()) R=Mid;
else L=Mid;
}
printf("%.3lf\n",R);
}
return ;
} int Aptal=Presist();
int main(int argc,char**argv){;}
T掉的Kruskal
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath> #define max(a,b) (a>b?a:b) inline void read(int &x)
{
x=; register char ch=getchar();
for(; ch>''||ch<''; ) ch=getchar();
for(; ch>=''&&ch<=''; ch=getchar()) x=x*+ch-'';
} const double INF(10000000.0);
const double eps(1e-);
const int N(); double h[N][N],d[N][N];
struct Node {
int x,y,h;
}city[N];
int n; double L,R,Mid,ans,dis[N];
bool vis[N]; inline double Dis(Node a,Node b)
{
double x=1.0*(a.x-b.x)*(a.x-b.x);
double y=1.0*(a.y-b.y)*(a.y-b.y);
return (double)sqrt(x+y);
} inline bool check()
{
for(int i=; i<=n; ++i) vis[i]=;
for(int i=; i<=n; ++i) dis[i]=h[][i]-Mid*d[][i];
double ret=0.0,minn; vis[]=;
for(int i=,u; i<=n; ++i)
{
minn=INF;
for(int j=; j<=n; ++j)
if(!vis[j]&&minn>dis[j]) minn=dis[u=j];
if(minn==INF) break;
ret+=minn; vis[u]=;
for(int v=; v<=n; ++v)
if(!vis[v]&&dis[v]>h[u][v]-Mid*d[u][v])
dis[v]=h[u][v]-Mid*d[u][v];
}
return ret<=;
} int Presist()
{
for(; scanf("%d",&n)&&n; )
{
for(int i=; i<=n; ++i)
{
read(city[i].x),
read(city[i].y),
read(city[i].h),
R=max(R,city[i].h);
}
for(int i=; i<=n; ++i)
for(int j=i+; j<=n; ++j)
{
d[i][j]=d[j][i]=Dis(city[i],city[j]);
h[i][j]=h[j][i]=abs(city[i].h-city[j].h)*1.0;
}
for(L=; L+eps<R; )
{
Mid=(L+R)/2.0;
if(check()) R=Mid;
else L=Mid;
}
printf("%.3lf\n",R);
}
return ;
} int Aptal=Presist();
int main(int argc,char**argv){;}
最新文章
- 新浪ip地址转换接口
- 在windows 下安装启动redis
- Python OpenCV —— Arithmetic
- springMVC下载FTP上的文件
- Linux命令(2) - 查看目录和文件大小: du -sh
- Python学习教程(learning Python)--1.2.3 Python格式化输出百分比
- Selenium如何使用自定义的Firefox配置文件?
- codeforces #256 A. Rewards
- Python第二十二天 stat模块 os.chmod方法 os.stat方法 pwd grp模块
- C语言学生管理系统(原版本)(自编)
- c#套料程序设计
- [Git] git log命令
- 每日一练之贪心算法(P2587)
- 自写Jquery插件 Tab
- C# Web 数据注解Data Annotations、模型状态ModelState、数据验证
- 【LOJ】#2533. 「CQOI2018」交错序列
- Java 之 POI各Jar包作用
- python 保留两位小数
- hbase使用MapReduce操作1(基本增删改查)
- PHP中普通属性和静态属性