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