poj 2728 Desert King（最优比例生成树，01分数规划）

poj 2728 Desert King（最优比率生成树，01分数规划）

http://poj.org/problem?id=2728

大致题意：有n个村庄，输入每个村庄的位置和高度，这n个村庄要连在一起，村与村之间的长度为他们之间的欧几里得距离，花费是两村之间的高度差，要求连在一起的花费和与距离和之比的最小值。

思路：明显的最优比率生成树。二分答案λ，每条边重新赋权c[i] - λd[i] ，因为要求比值最小，那么对于所有的生成树，它们的f[λ]必须>=0，所以只需求得基于最小生成树的f'[λ]，当f'[λ] = 0时即找到了正解λ*。

二分：

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#define LL long long
#define _LL __int64
#define eps 1e-7
using namespace std;
const _LL INF = 1e18;
const int maxn = 1010;

struct node
{
	int x,y,z;
}p[maxn];

int n;
double Map[maxn][maxn];

double cal(int i, int j)
{
	return sqrt( 1.0*(p[i].x - p[j].x)*(p[i].x - p[j].x) + 1.0*(p[i].y - p[j].y)*(p[i].y - p[j].y) );
}

double prim(double mid)
{
	double dis[maxn];
	int vis[maxn];
	double sum = 0;
	memset(vis,0,sizeof(vis));
	for(int i = 1; i <= n; i++)
		dis[i] = abs(p[i].z - p[1].z) - Map[1][i] * mid;

	vis[1] = 1;
	for(int i = 1; i <= n-1; i++)
	{
		double Min = INF;
		int pos = -1;
		for(int j = 1; j <= n; j++)
		{
			if(!vis[j] && dis[j] < Min)
			{
				Min = dis[j];
				pos = j;
			}
		}
		if(pos == -1)
			break;
		sum += Min;
		vis[pos] = 1;

		double tmp;
		for(int j = 1; j <= n; j++)
		{
			tmp = abs(p[pos].z - p[j].z) - Map[pos][j] * mid;
			if(!vis[j] && dis[j] > tmp)
				dis[j] = tmp;
		}
	}

	return sum;
}

int main()
{
	while(~scanf("%d",&n) && n)
	{
		for(int i = 1; i <= n; i++)
			scanf("%d %d %d",&p[i].x,&p[i].y,&p[i].z);

		for(int i = 1; i <= n; i++)
		{
			for(int j = 1; j <= n; j++)
				Map[i][j] = cal(i,j);
		}

		double l = 0.0, r = 40.0;
		double mid;
		while(fabs(r-l) > eps)
		{
			mid = (l+r)/2;
			if( prim(mid) >= 0)
				l = mid;
			else r = mid;
		}
		printf("%.3f\n",mid);
	}
	return 0;
}

迭代

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#define LL long long
#define _LL __int64
#define eps 1e-7
using namespace std;
const _LL INF = 1e18;
const int maxn = 1010;

struct node
{
	int x,y,z;
}p[maxn];

int n;
double Map[maxn][maxn];

double cal(int i, int j)
{
	return sqrt( 1.0*(p[i].x - p[j].x)*(p[i].x - p[j].x) + 1.0*(p[i].y - p[j].y)*(p[i].y - p[j].y) );
}

double prim(double mid)
{
	double cost,len,sum;
	double dis[maxn];
	int vis[maxn];
	int pre[maxn];

	sum = 0;
	cost = 0;
	len = 0;
	memset(vis,0,sizeof(vis));
	memset(pre,-1,sizeof(pre));
	for(int i = 1; i <= n; i++)
	{
		dis[i] = abs(p[i].z - p[1].z) - Map[1][i] * mid;
		pre[i] = 1;
	}
	vis[1] = 1;

	for(int i = 1; i <= n-1; i++)
	{
		double Min = INF;
		int pos = -1;
		for(int j = 1; j <= n; j++)
		{
			if(!vis[j] && dis[j] < Min)
			{
				Min = dis[j];
				pos = j;
			}
		}
		if(pos == -1)
			break;
		sum += Min;
		cost += abs(p[ pre[pos] ].z - p[pos].z);
		len += Map[pre[pos]][pos];
		vis[pos] = 1;

		double tmp;
		for(int j = 1; j <= n; j++)
		{
			tmp = abs(p[pos].z - p[j].z) - Map[pos][j] * mid;
			if(!vis[j] && dis[j] > tmp)
			{
				dis[j] = tmp;
				pre[j] = pos;
			}
		}
	}
	return cost/len;
}

int main()
{
	while(~scanf("%d",&n) && n)
	{
		for(int i = 1; i <= n; i++)
			scanf("%d %d %d",&p[i].x,&p[i].y,&p[i].z);

		for(int i = 1; i <= n; i++)
		{
			for(int j = 1; j <= n; j++)
				Map[i][j] = cal(i,j);
		}

		double l = 0.0,r;
		while(1)
		{
			r = prim(l);
			if(fabs(r-l) < eps) break;
			l = r;
		}
		printf("%.3f\n",r);
	}
	return 0;
}