poj 2728 Desert King(最小比率生成树 / 0-1分数规划 / 二分)
程序员文章站
2022-07-13 13:52:56
...
二分答案,我们要找最小的答案,如果有更小的答案说明
∑
W
−
Z
∗
∑
L
<
=
0
∑W−Z∗∑L <= 0
∑W−Z∗∑L<=0。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int N = 500007, INF = 0x3f3f3f3f;
const double eps = 1e-6;
double dist[N];
int x[N], y[N], z[N];
int n, m;
bool vis[N];
double get_dist(int a, int b){
return sqrt((x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] - y[b]));
}
bool check(double x){
fill(dist, dist + 1 + n, INF);
memset(vis, 0, sizeof vis);
double ans = 0.0;
dist[1] = 0.0;
for(int i = 1; i <= n; ++ i){
int t = -1;
for(int j = 1; j <= n; ++ j){
if(!vis[j] && (t == -1 || dist[j] < dist[t]))
t = j;
}
vis[t] = 1;
ans += dist[t];
for(int j = 1;j <= n;++ j){
if(!vis[j] && dist[j] > fabs(z[j] - z[t]) - get_dist(t, j) * x + eps)
dist[j] = fabs(z[j] - z[t]) - get_dist(t, j) * x;
}
}
return ans >= 0.0;
}
int main(){
while(~scanf("%d", &n) && n){
for(int i = 1; i <= n; ++ i){
scanf("%d%d%d", &x[i], &y[i], &z[i]);
}
double l = 0.0, r = 10000001.0;
while((r - l) > eps){
double mid = (l + r) / 2;
if(check(mid))l = mid;
else r = mid;
}
printf("%.3f\n", l);
}
}
/*
x=w/l -> w-l*x =0
f(x) = w-l*x;
将边权更改为w-l*x来求生成树
因为f(x)是个单调递减函数,随着x的增大而减少
对于任意一个生成树如果
f(x)>0 则 l需要增大
f(x)<0 否则 l需要减小
若要满足f(x)==0恒成立
1.若要x取最大值,则不能存在任意一个生成树f(x)>0,否则x还能继续增大,即任意生成树f(x)<=0
若存在一个生成树f(x)>0,则那个生成树的比率一定大于当前x,w/l > x -> w-l*x > 0
2.若要x取最小值,则不能存在任意一个生成树f(x)<0,否则x还能继续减小,即任意生成树f(x)>=0
若存在一个生成树f(x)<0,则那个生成树的比率一定小于当前x,w/l < x -> w-l*x < 0
若要满足f(x)>0恒成立,则最小生成树>0
若要满足f(x)<0恒成立,则最大生成树<0
此题目求解最小的x值,也就是检查是否所有的生成树f(x)>=0,即最小生成树>=0
如果最小生成树大于0,所有的生成树都满足f(x)>0,尝试增加x得到f(x)=0
否则,有生成树不满足这个条件,那么x一定要减少来使所有f(x)>=0
kur边数较多,复杂度(mlog*log)排序加二分,过不去
使用prim算法
*/