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 閱讀(551) 評論(2) 編輯收藏引用

FeedBack:

# re: 最優比例生成樹

2009-01-19 15:48 | 菠蘿東西

我也按照黑書上的寫，改來改去還是Tle，難道要改成迭代？？回復更多評論

# re: 最優比例生成樹[未登錄]

2009-01-20 08:54 | Knight

@菠蘿東西
代碼我發到你郵箱了。回復更多評論

刷新評論列表

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！



網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

2009年1月

日

一

二

三

四

五

六

常用鏈接

留言簿(8)

隨筆檔案

文章檔案

2009年3月 (1)

常用鏈接

留言簿(8)

隨筆檔案

文章檔案

Friends

OJ

搜索

最新評論

閱讀排行榜

評論排行榜