posts - 74,  comments - 33,  trackbacks - 0
最优比例生成树
http://hi.baidu.com/zzningxp/blog/item/b2d1b4ec1f8bbc2262d09fc9.html

http://acm.pku.edu.cn/JudgeOnline/problem?id=2728 可以试试这道题。。。
思路AC后更新
已经ac，很慢。。。。巨慢！
部分代码如下：
double prim(int n,double rat)
{
    int i,j,sign;
    int flag[1000];
    double dis[1000],sum;
    memset(flag,0,sizeof(flag));
    for(i=0;i<n;i++)
        for(j=i;j<n;j++)
        {
            double t=DIS(i,j)-map[i][j]*rat;
            cost[i][j]=t;
            cost[j][i]=t;
        }
    for(i=0;i<n;i++)
        dis[i]=cost[0][i];
    flag[0]=1;
    sum=0;
    for(j=1;j<n;j++)
    {
        double min=100000000;
        for(i=0;i<n;i++)
            if(!flag[i]&&min>dis[i])
            {
                sign=i;
                min=dis[i];    
            }
        flag[sign]=1;
        sum+=dis[sign];
        for(i=0;i<n;i++)
            if(!flag[i]&&dis[i]>cost[sign][i])
                dis[i]=cost[sign][i];    
    }
    return sum;    
}
二分思想代码如下：
while(1)
        {
            mid=(low+high)/2;
            double t=prim(n,mid);
            if(fabs(t)<1e-6)break;
            if(t<0)high=mid;
            else low=mid;
        }

posted on 2009-01-06 18:23 KNIGHT 阅读(537) 评论(2)  编辑 收藏 引用

FeedBack:
# re: 最优比例生成树
2009-01-19 15:48 | 菠萝东西
我也按照黑书上的写，改来改去还是Tle，难道要改成迭代？？  回复  更多评论
  
# re: 最优比例生成树[未登录]
2009-01-20 08:54 | Knight
@菠萝东西
代码我发到你邮箱了。  回复  更多评论
  

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


Copyright ©2024 KNIGHT Powered By: 博客园 模板提供：沪江博客
<2009年4月>
日一二三四五六
2930311234
567891011
12131415161718
19202122232425
262728293012
3456789

常用链接

留言簿(8)

随笔档案

文章档案

Friends

OJ

搜索

  •  

最新评论

阅读排行榜

评论排行榜