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   知识库   博问   管理


<2009年1月>
28293031123
45678910
11121314151617
18192021222324
25262728293031
1234567

常用链接

留言簿(8)

随笔档案

文章档案

Friends

OJ

搜索

  •  

最新评论

阅读排行榜

评论排行榜