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 阅读(532) 评论(2) 编辑收藏引用

FeedBack:

# re: 最优比例生成树

2009-01-19 15:48 | 菠萝东西

我也按照黑书上的写，改来改去还是Tle，难道要改成迭代？？回复更多评论

# re: 最优比例生成树[未登录]

2009-01-20 08:54 | Knight

@菠萝东西
代码我发到你邮箱了。回复更多评论

刷新评论列表

只有注册用户登录后才能发表评论。




网站导航: 博客园 IT新闻 BlogJava 知识库博问管理

2009年1月

日

一

二

三

四

五

六

常用链接

留言簿(8)

随笔档案

文章档案

2009年3月 (1)

常用链接

留言簿(8)

随笔档案

文章档案

Friends

OJ

搜索

最新评论

阅读排行榜

评论排行榜