Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

我想不通,为什么一定要在SPFA的时候去计算边权,难道不能事先在二分出mid的时候就立即建一副新图呢?

Posted by bingshen at 2011-02-18 00:59:50 on Problem 3621
也就是说为什么一定要这样:
node p=map[u][i];
w=p.len*mid-happy[p.v];
if(dis[p.v]>dis[u]+w)
{
	dis[p.v]=dis[u]+w;
        if(!used[p.v])
}

而不能事先进行如下操作

build(double mid)
{
       int i,j;
       for(i=1;i<=n;i++)
             for(j=0;j<map[i].size();j++)
                    map[i][j].len=happy[map[i][j]]-mid*map[i][j].len;
}

而且我还有个问题,按照公式
假设最大比率为r
r=sigma(happy[i])/sigma(len[i]);
边形后应该等于r*sigma(len[i])-sigma(happy[i])=0
---->sigma(len[i]*r-happy[i])=0
也就是说是len[i]*r-happy[i]才对呀,为什么要用他的相反数来做边权呢?
我好迷茫,跪求大牛解释。。。或者加我的QQ510685263 小弟不胜感激!!!

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator