The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

POJ 2728 Desert King(最优比率生成树) prim+二分

北京赛区的经典题目,最优比率生成树,传说中楼哥1A的G题。。。
什么是最优比率生成树呢?说白了很简单,已知一个完全图,每条边有两个参数(b和c),求一棵生成树,使(∑xi×ci)/(∑xi×bi)最小,其中xi当第i条边包含在生成树中时为1,否则为0。其实也可以看成一个0,1的整数规划问题。
我的做法是LRJ《算法艺术与信息学竞赛》中介绍的二分,详细的证明请看书,这里只是简单的介绍一下核心的方法:
1.首先找出这个比率的最小值和最大值 front,rear
2.求mid=(front+reat)/2
3.用 ci-mid*bi 重新构图
4.求出新图的最小生成树权值之和
5.如果权值等于0,mid就是我们要求的比率,结束。如果权值>0,front=mid,如果权值<0,rear=mid,跳回2继续循环。


不过这个算法对精度的要求比较高,我用0.001就错了,0.00001超时,只有0.0001AC,汗
另外时间效率也不高,3000MS的题,耗去了2500MS,看来这个算法还是有待改进。
下面是我的代码:

#include<iostream>
#include
<algorithm>
#include
<cstring>
#include
<cmath>
using namespace std;
#define MAX 1001
#define INF 1000000000
struct node
{

    
double x,y,h;
}
dot[MAX];


inline 
double dis(double x1,double y1,double x2,double y2)
{

    
return sqrt( (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1) );
}



double graph[MAX][MAX];

inline 
void creat(int n,double l)
{
    
int i,j;
    
for(i=1;i<=n;i++)
    
{

        
for(j=1;j<=n;j++)
        
{

            graph[i][j]
=fabs(dot[i].h-dot[j].h)-l*dis(dot[i].x,dot[i].y,dot[j].x,dot[j].y);
        }

    }

}


inline 
double prim(double graph[MAX][MAX],int n)
{
    
bool visit[MAX]={0};
    
int mark;
    
double dis[MAX];
    
double ans=0;
    
int i,j;
    visit[
1]=true;
    
for(i=1;i<=n;i++)
        dis[i]
=graph[1][i];
    
for(i=1;i<n;i++)
    
{

        
int minnum=INF;
        
for(j=1;j<=n;j++)
        
{

            
if(!visit[j]&&dis[j]<=minnum)
            
{
                minnum
=dis[j];
                mark
=j;
            }

        }

        visit[mark]
=true;
        ans
+=dis[mark];
        
for(j=1;j<=n;j++)
        
{
            
if(!visit[j]&&graph[mark][j]<dis[j])
                dis[j]
=graph[mark][j];
        }


    }

    
return ans;
}



int main()
{

    
int i,j;
    
int n;
    
double res;
    
while(scanf("%d",&n))
    
{

        
if(n==0)
            
break;
        
for(i=1;i<=n;i++)
        
{
            scanf(
"%lf%lf%lf",&dot[i].x,&dot[i].y,&dot[i].h);
        }

        
double front,rear;
        front
=0;
        rear
=100;//这个地方有点悬。。。
        double mid;
        
double pre=0.0;
        
while(front<=rear)
        
{

            mid
=(front+rear)/2;
            creat(n,mid);
            res
=prim(graph,n);
            
if(fabs(res-pre)<=0.0005)
                
break;
            
else if(res>0.0005)
                front
=mid;
            
else
                rear
=mid;
        }

        printf(
"%.3lf\n",mid);
    }

    
return 0;
}

———————————————————————传说中的分割线————————————————————————————
终于在今天下午 使用迭代法将此题优化到282MS,呵呵 这名字让我又想起了数值分析。。。
#include<iostream>
#include
<algorithm>
#include
<cstring>
#include
<cmath>
using namespace std;
#define MAX 1001
#define INF 1000000000
struct node
{
    
double x,y,h;
}
dot[MAX];


inline 
double dis(double x1,double y1,double x2,double y2)
{

    
return sqrt( (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1) );
}



double graph[MAX][MAX];
double c[MAX][MAX];
double s[MAX][MAX];

inline 
void creatcs(int n)
{
    
int i,j;
    
for(i=1;i<=n;i++)
    
{
        
for(j=1;j<=n;j++)
        
{
            c[i][j]
=fabs(dot[i].h-dot[j].h);
            s[i][j]
=dis(dot[i].x,dot[i].y,dot[j].x,dot[j].y);
        }

    }

}



inline 
void creat(int n,double l)
{
    
int i,j;
    
for(i=1;i<=n;i++)
    
{

        
for(j=1;j<=n;j++)
        
{

            graph[i][j]
=c[i][j]-l*s[i][j];
        }

    }

}

double sumc;
double sums;

inline 
void prim(double graph[MAX][MAX],int n)
{
    sumc
=0;
    sums
=0;
    
bool visit[MAX]={0};
    
int mark;
    
int pre[MAX];
    
double dis[MAX];
    
int i,j;
    visit[
1]=true;
    
for(i=1;i<=n;i++)
    
{
        dis[i]
=graph[1][i];
        pre[i]
=1;
    }

    
for(i=1;i<n;i++)
    
{

        
int minnum=INF;
        
for(j=1;j<=n;j++)
        
{

            
if(!visit[j]&&dis[j]<=minnum)
            
{
                minnum
=dis[j];
                mark
=j;
            }

        }

        visit[mark]
=true;
        sumc
+=c[pre[mark]][mark];
        sums
+=s[pre[mark]][mark];
        
for(j=1;j<=n;j++)
        
{
            
if(!visit[j]&&graph[mark][j]<dis[j])
            
{
                dis[j]
=graph[mark][j];
                pre[j]
=mark;
            }

        }


    }

}



int main()
{

    
int i,j;
    
int n;
    
while(scanf("%d",&n))
    
{

        
if(n==0)
            
break;
        
for(i=1;i<=n;i++)
        
{
            scanf(
"%lf%lf%lf",&dot[i].x,&dot[i].y,&dot[i].h);
        }

        creatcs(n);
        
double prerate=30.0;
        
double rate=30.0;
        
while(true)
        
{
            creat(n,rate);
            prim(graph,n);
            rate
=sumc/sums;
            
if(fabs(rate-prerate)<0.001)
                
break;
            prerate
=rate;
        }

        printf(
"%.3lf\n",rate);
    }

    
return 0;
}

posted on 2009-09-04 23:53 abilitytao 阅读(2780) 评论(4)  编辑 收藏 引用

评论

# re: POJ 2728 Desert King(最优比率生成树) prim+二分 2009-09-05 12:05 凡客诚品

不错哦  回复  更多评论   

# re: POJ 2728 Desert King(最优比率生成树) prim+二分 2009-09-08 14:58 戴尔电脑

世界的发生的纠纷  回复  更多评论   

# re: POJ 2728 Desert King(最优比率生成树) prim+二分 2009-09-09 01:26 abilitytao

@戴尔电脑
做广告的不妨给我们团队赞助吧 呵呵 要写也要写点有意义的东西 否则删除 警告!  回复  更多评论   

# re: POJ 2728 Desert King(最优比率生成树) prim+二分 2009-09-09 22:29 Vincent

楼哥1a...很正常- -  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理