题目 http://poj.org/problem?id=2728
关键词：0/1分数规划，参数搜索，二分法，dinkelbach
参考资料：http://hi.baidu.com/zzningxp/item/28aa46e0fd86bdc2bbf37d03
http://hi.baidu.com/zheng6822/item/b31fbe9d5ae17536336eeb8f
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<stdlib.h>
#include<math.h>
#define N 1010
#define INF 1e15
#define eps 1e-10
using namespace std;
double X[N],Y[N],Z[N];
double cost[N][N];
double lowcost[N];
int closest[N];int vis[N];
int n;double r;
double disc(int i,int j)
{
return fabs(Z[i]-Z[j]);
}
double disd(int i,int j)
{
return sqrt((X[i]-X[j])*(X[i]-X[j])+(Y[i]-Y[j])*(Y[i]-Y[j]));
}
double prim(double r)
{
double sumc=;double sumd=;
for(int i=;i<n;i++)
for(int j=;j<n;j++)
{
if(i==j)
cost[i][j]=INF;
else
cost[i][j]=disc(i,j)-r*disd(i,j);
}
for(int i=;i<n;i++)
{
lowcost[i]=cost[][i];
vis[i]=;
closest[i]=;
}
closest[]=;
vis[]=;
int k;
for(int i=;i<n;i++)
{
double tmp=INF;
for(int j=;j<n;j++)
if(!vis[j]&&tmp>lowcost[j])
{
k=j;
tmp=lowcost[j];
}
vis[k]=;
for(int j=;j<n;j++)
if(!vis[j]&&lowcost[j]>cost[k][j])
{
lowcost[j]=cost[k][j];
closest[j]=k;
}
}
for(int i=;i<n;i++)
{
sumc+=disc(i,closest[i]);
sumd+=disd(i,closest[i]);
}
return sumc/sumd;
}
int main()
{
while(scanf("%d",&n)!=EOF&&n)
{
for(int i=;i<n;i++)
cin>>X[i]>>Y[i]>>Z[i];
double r1=,r2=;
while()
{
r2=prim(r1);
if(fabs(r1-r2)<=eps)
break;
r1=r2;
}
printf("%.3f\n",r1);
}
return ;
}
PRIM+迭代法
主要算法部分的分析
double prim(double r)
{
/*根据题目要求和算法得到由新的权值组成的图，并且写出邻接矩阵*/
double sumc=0;double sumd=0;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
if(i==j)
cost[i][j]=INF;
else
cost[i][j]=disc(i,j)-r*disd(i,j);
}
/*初始化*/
for(int i=0;i<n;i++)
{
lowcost[i]=cost[0][i];
vis[i]=0; /*判断该点是否已经在集合内*/
closest[i]=0; /*邻接点*/
}
/*将第一个点加入集合*/
closest[0]=0;
vis[0]=1;
int k;
for(int i=0;i<n;i++)
{
double tmp=INF;
/*通过一次循环找到与第一个点距离最短的点*/
for(int j=0;j<n;j++)
if(!vis[j]&&lowcosat[j]<tmp)
{
k=j;
tmp=lowcost[j];
}
/*将该点加入集合中*/
vis[k]=1;
/*这一步是更新其他的点到集合中的点的距离，closest是用来记录该点的前驱的点的数组，lowcost是用来记录其他点到MST的最短距离的数组，注意是到树上任意一点而不是其中某点*/
for(int j=0;j<n;j++)
if(!vis[j]&&lowcost[j]>cost[j][k])
{
lowcost[j]=cost[j][k];
closest[j]=k;
}
}
/*返回参数，用于迭代*/
for(int i=0;i<n;i++)
{
sumc+=disc(i,closest[i]);
sumd+=disd(i,closest[i]);
}
return sumc/sumd;
}