pku 2728 Desert King最有比率生成ツリー
7022 ワード
http://poj.org/problem?id=2728
タイトル:
n個の点の座標の1級の各点に対応する高さを与え、各辺の2つの値、a[i][j]=fabs(h[i]-h[j])の高さ差は修i->jという道にはa[i][j]の費用が必要であり、b[i][j]は道の長さを表す.すべての点が互いに通じ合い、総費用/道路の総長さが最小になるように、道路を修理させます.
考え方:最小比率生成ツリー.このリンクで説明する01スコア計画に従って、最も比率のあるツリーを生成します.
最小生成ツリーの保証を求めて値を最小にするために,二分列挙解を求めた.そしてf(l)==0の解が得られたのが我々の結果である.
Dinkelbach反復アルゴリズムの解決
サブ問題の最適解をprim()ごとに求め,ある範囲内になるまでrを代入する..
タイトル:
n個の点の座標の1級の各点に対応する高さを与え、各辺の2つの値、a[i][j]=fabs(h[i]-h[j])の高さ差は修i->jという道にはa[i][j]の費用が必要であり、b[i][j]は道の長さを表す.すべての点が互いに通じ合い、総費用/道路の総長さが最小になるように、道路を修理させます.
考え方:最小比率生成ツリー.このリンクで説明する01スコア計画に従って、最も比率のあるツリーを生成します.
最小生成ツリーの保証を求めて値を最小にするために,二分列挙解を求めた.そしてf(l)==0の解が得られたのが我々の結果である.
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <string>
#define CL(a,num) memset((a),(num),sizeof(a))
#define iabs(x) ((x) > 0 ? (x) : -(x))
#define Min(a,b) (a) > (b)? (b):(a)
#define Max(a,b) (a) > (b)? (a):(b)
#define ll long long
#define inf 0x7f7f7f7f
#define MOD 1073741824
#define lc l,m,rt<<1
#define rc m + 1,r,rt<<1|1
#define pi acos(-1.0)
#define test puts("<------------------->")
#define maxn 100007
#define M 150
#define N 1007
using namespace std;
/*
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
*/
//freopen("din.txt","r",stdin);
const double eps = 1e-6;
struct node
{
double x,y,z;
}p[N];
double dis[N];
bool vt[N];
double a[N][N];
double b[N][N];
int n;
int dblcmp(double x)
{
if (x > eps) return 1;
else if (x < -eps) return -1;
else return 0;
}
void init()
{
int i,j;
for (i = 0; i < n; ++i)
{
for (j = 0; j < n; ++j)
{
a[i][j] = b[i][j] = (i != j)*inf;
}
}
}
double prim(double m)
{
int i,j;
double res = 0;
for (i = 0; i <= n; ++i)
{
vt[i] = false;
dis[i] = a[0][i] - m*b[0][i];
}
dis[0] = 0; vt[0] = true;
for (int k = 0; k < n - 1; ++k)
{
double MIN = inf;
for (i = 0; i < n; ++i)
{
if (!vt[i] && dis[i] < MIN)
{
j = i;
MIN = dis[i];
}
}
res += MIN;
vt[j] = true;
for (i = 0; i < n; ++i)
{
double t = a[j][i] - m*b[j][i];// ， 【j,i】 【i,j】 tle
if (!vt[i] && b[j][i] != inf && dis[i] > t)
{
dis[i] = t;
}
}
}
return res;
}
int main()
{
//freopen("input.txt","r",stdin);
int i,j;
while (~scanf("%d",&n))
{
if (!n) break;
for (i = 0; i < n; ++i)
scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].z);
init();
double r = -1;
for (i = 0; i < n; ++i)
{
for (j = 0; j < n; ++j)
{
if (i == j) continue;
double cb = sqrt((p[i].x - p[j].x)*(p[i].x - p[j].x) + (p[i].y - p[j].y)*(p[i].y - p[j].y));
double ca = iabs(p[i].z - p[j].z);
b[i][j] = b[j][i] = cb;
a[i][j] = a[j][i] = ca;
r = max(r,ca);
}
}
double l = 0;
double mid = 0;
while (dblcmp(l - r) < 0)
{
mid = (l + r)/2;
if (prim(mid) >= 0)
{
l = mid;
}
else r = mid;
}
printf("%.3lf
",mid);
}
return 0;
}
Dinkelbach反復アルゴリズムの解決
サブ問題の最適解をprim()ごとに求め,ある範囲内になるまでrを代入する..
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <string>
#define CL(a,num) memset((a),(num),sizeof(a))
#define iabs(x) ((x) > 0 ? (x) : -(x))
#define Min(a,b) (a) > (b)? (b):(a)
#define Max(a,b) (a) > (b)? (a):(b)
#define ll long long
#define inf 0x7f7f7f7f
#define MOD 1073741824
#define lc l,m,rt<<1
#define rc m + 1,r,rt<<1|1
#define pi acos(-1.0)
#define test puts("<------------------->")
#define maxn 100007
#define M 150
#define N 1007
using namespace std;
/*
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
*/
//freopen("din.txt","r",stdin);
const double eps = 1e-6;
struct node
{
double x,y,z;
}p[N];
double dis[N];
bool vt[N];
double a[N][N];
double b[N][N];
int pre[N];
int n;
int dblcmp(double x)
{
if (x > eps) return 1;
else if (x < -eps) return -1;
else return 0;
}
void init()
{
int i,j;
for (i = 0; i < n; ++i)
{
for (j = 0; j < n; ++j)
{
a[i][j] = b[i][j] = (i != j)*inf;
}
}
}
double prim(double m)
{
int i,j;
double tval = 0,tdis = 0;
for (i = 0; i <= n; ++i)
{
vt[i] = false;
dis[i] = a[0][i] - m*b[0][i];
pre[i] = 0;
}
dis[0] = 0; vt[0] = true;
pre[0] = -1;
for (int k = 0; k < n - 1; ++k)
{
double MIN = inf;
for (i = 0; i < n; ++i)
{
if (!vt[i] && dis[i] < MIN)
{
j = i;
MIN = dis[i];
}
}
tval += a[pre[j]][j];//
tdis += b[pre[j]][j];//
vt[j] = true;
for (i = 0; i < n; ++i)
{
double t = a[j][i] - m*b[j][i];
if (!vt[i] && b[j][i] != inf && dis[i] > t)
{
pre[i] = j;
dis[i] = t;
}
}
}
return tval/tdis;//
}
int main()
{
//freopen("input.txt","r",stdin);
int i,j;
while (~scanf("%d",&n))
{
if (!n) break;
for (i = 0; i < n; ++i)
scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].z);
init();
for (i = 0; i < n; ++i)
{
for (j = 0; j < n; ++j)
{
if (i == j) continue;
double cb = sqrt((p[i].x - p[j].x)*(p[i].x - p[j].x) + (p[i].y - p[j].y)*(p[i].y - p[j].y));
double ca = iabs(p[i].z - p[j].z);
b[i][j] = b[j][i] = cb;
a[i][j] = a[j][i] = ca;
}
}
double s = 0,r = 0;
while (1)
{
r = prim(s);
if (dblcmp(s - r) == 0) break;
s = r;
}
printf("%.3lf
",r);
}
return 0;
}