poj 2728(最小比率生成树)

参考题解：http://www.cppblog.com/jh818012/articles/167743.html

题意：有n个村庄，村庄在不同坐标和海拔，现在要对所有村庄供水，只要两个村庄之间有一条路即可，

建造水管距离为坐标之间的欧几里德距离（好象是叫欧几里德距离吧），费用为海拔之差

现在要求方案使得费用与距离的比值最小

很显然，这个题目是要求一棵最优比率生成树，

0-1分数规划，0-1分数规划是分数规划的一种特殊情况，分数规划适用于求解最优化问题的，对于求最大的对应解，该理论也有效

这是从网上找到的具体的最优比率生成树的方法的讲解

////////////////////

概念

有带权图G, 对于图中每条边e[i], 都有benifit[i](收入)和cost[i](花费), 我们要求的是一棵生成树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<m .

为了使 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) < max(r). 矛盾;

　　若z( max(r) ) >= 0, 根据性质1, 当z = 0 时r最大.

View Code

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 #include<queue>
 7 using namespace std;
 8 #define N 1010
 9 #define MAX 999999999
10 const double eps=1e-4;
11 int n;
12 int vis[N],x[N],y[N],z[N],pre[N];
13 double dis[N],cost[N][N],dist[N][N];
14 double prim(double x){
15     double totalcost=0,totaldist=0;
16     for(int i=1;i<=n;i++){
17         pre[i]=1;
18     }
19     dis[1]=0;
20     memset(vis,0,sizeof(vis));
21     vis[1]=1;
22     for(int i=2;i<=n;i++){
23         dis[i]=cost[1][i]-dist[1][i]*x;
24     }
25     int k;
26     for(int i=2;i<=n;i++){
27         double mincost=MAX;
28         for(int j=2;j<=n;j++){
29             if(!vis[j]&&dis[j]<mincost){
30                 mincost=dis[j];
31                 k=j;
32             }
33         }
34         vis[k]=1;
35         totalcost+=cost[pre[k]][k];
36         totaldist+=dist[pre[k]][k];
37         for(int j=1;j<=n;j++){
38             if(!vis[j]&&dis[j]>cost[k][j]-dist[k][j]*x){
39                 dis[j]=cost[k][j]-dist[k][j]*x;
40                 pre[j]=k;
41             }
42         }
43     }
44     return totalcost/totaldist;
45 }
46 int main(){
47     while(scanf("%d",&n),n){
48         for(int i=1;i<=n;i++){
49             scanf("%d%d%d",&x[i],&y[i],&z[i]);
50             for(int j=1;j<i;j++){
51                 double t=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
52                 cost[i][j]=cost[j][i]=abs(z[i]-z[j]);
53                 dist[i][j]=dist[j][i]=sqrt(t);
54             }
55         }
56         double a=0;
57         while(1){
58             double b=prim(a);
59             if(abs(a-b)<eps)break;
60             else a=b;
61             //cout<<a<<endl;
62         }
63         printf("%.3f\n",a);
64     }
65     return 0;
66 }