POJ 2728 Desert King(最优比率生成树) 最小生成树

POJ 2728 Desert King(最优比率生成树)

题目大意

有n个村庄，村庄在不同坐标和海拔，现在要对所有村庄供水，只要两个村庄之间有一条路即可，建造水管距离为坐标之间的欧几里德距离，费用为海拔之差，现在要求方案使得费用与距离的比值最小，很显然，这个题目是要求一棵最优比率生成树。
分析
以下内容摘录自网上(其他博客排版太丑重排了一下)
【POJ 2728 Desert King(最优比率生成树)】概念
有带权图G, 对于图中每条边e[i], 都有benifiti和costi, 我们要求的是一棵生成树T, 它使得

∑(benifit[i])∑(cost[i])i∈T
最大(或最小).这显然是一个具有现实意义的问题.
解法之一 0-1分数规划
设 x[i]等于1或0, 表示边 e[i]是否属于生成树.
则我们所求的比率 r=∑(benifit[i]?x[i])∑(cost[i]?x[i]),0≤i
为了使 r 最大, 设计一个子问题: 让 z=∑(benifit[i]?x[i])?l?∑(cost[i]?x[i])=∑(d[i]?x[i])最大(d[i] = benifit[i] - l * cost[i]) ,并记为z(l) .我们可以兴高采烈地把z(l)$看做以d为边权的最大生成树的总权值.
然后明确两个性质:
1. z单调递减
  证明: 因为cost为正数, 所以z随l的减小而增大.
2. z(max(r))=0
  证明: 若 z(max(r))<0,∑(benifit[i]?x[i])?max(r)?∑(cost[i]?x[i])<0 ,
  可化为 max(r) 若 z(max(r))>=0 , 根据性质1, 当z = 0 时r最大.
?
?
代码

#include #include #include #include #include #include #include #include #include #include using namespace std; const double INF=0x3f3f3f3f; const intMAXN=1005; const double eps=1e-7; int n; double dist[MAXN]; //dist[i]表示当前找到的最小生成子树到节点i的边的最小值 bool vis[MAXN]; double benefit[MAXN][MAXN]; //两个村庄之间的收益 double cost[MAXN][MAXN]; //两个村庄之间的花费 double edge[MAXN][MAXN]; //村庄之间的边权 struct Node { double x,y,z; }node[MAXN]; void Cal()//计算两两村庄间的收益(距离)和花费(海拔差) { for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { double tx=(node[i].x-node[j].x); double ty=(node[i].y-node[j].y); double tz=(node[i].z-node[j].z); benefit[i][j]=sqrt(tx*tx+ty*ty); cost[i][j]=fabs(tz); } } } double Prim() { memset(vis,0,sizeof(vis)); for(int i=1; i<=n; i++)dist[i]=INF; double min_edge; int min_node; double ans=0; //总的生成树边权 int now=1; //当前处理的节点 for(int i=1; i0.0000001) { M=(L+R)/2; for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) edge[i][j]=(cost[i][j]-M*benefit[i][j]); double t=Prim(); if(t>=0)L=M; else R=M; } return L; } int main() { int x,y,z; //(x,y)表示村庄坐标,z表示村庄海拔 double ans; while(scanf("%d",&n)!=0 && n!=0) { for(int i=1; i<=n; i++)scanf("%lf%lf%lf",&node[i].x,&node[i].y,&node[i].z); Cal(); ans=Binary_Work(); printf("%.3f\n",ans); } return 0; } /* 4 0 0 0 0 1 1 1 1 2 1 0 3 0 */