| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
我想不通,为什么一定要在SPFA的时候去计算边权,难道不能事先在二分出mid的时候就立即建一副新图呢?
也就是说为什么一定要这样:
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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator