zoj3408 Gao

//这题Gao死我了！！！

Gao

题意：Gao这个函数可以用来算出有向图中从0到达某点的最短路径条数，用Gao算出0到所有点的最短路径条数了，现问有多少条路径经过点v。输出答案的后10位。

解析：首先，这题有10000个点50000条边，对每点求最短路径是不可能的。观察最短路径以后我们可以知道，一个点v在一条最短路径里最多出现1次，要么出现在路径的末尾，要么出现在路径的中间，对于出现在末尾的最短路径数我们定义为cnt1[v]，而我们在计算0点到所有点的最短路径过程中是可以记录cnt1[v]的：

 

?
1
2
3
4
5
6
7
8
9
10
11
if(dis[u]+w<dis[v])                  //u->v权值为w
{
    dis[v]=dis[u]+w;
    cnt1[v]=cnt1[u];
    tmp.v=v;tmp.dis=dis[v];
    que.push(tmp);
}
else if(dis[u]+w==dis[v])
{   cnt1[v]+=cnt1[u];
    cnt1[v]%=MOD;
}

 

至于v出现在最短路径的中间的情况，定义cnt2[v]表示最短路径中从v出发的路径条数，那么根据组合数学定义,v出现在最短路中间的最短路径条数=cnt1[v]*cnt2[v]。cnt2[v]可以用Calc(v)进行递归计算(貌似也可以叫树形DP,好像还可以拓扑排序以后之间DP），假如有t1,t2,t3...tn与v邻接且v->t1,v->t2,v->t3...,v->tn都在最短路径上，那么同样根据组合数学加法原理有cnt2[v]=cnt2[t1]+cnt2[t2]+...cnt[tn]。因为t1,t2,tn都在最短路径上，所以cnt2[v]+=n;

最终ans[v]=cnt1[v]+cnt1[v]*cnt2[v]。

这题比较阴险的地方在于答案要保留后10位，而进行乘法的过程中会超long long（事实证明，在计算cnt1的过程中也会超long long，在这地方无限WA T_T）要用到布斯(Booth)乘法：

 

?
1
2
3
4
5
6
long long Mul(long long lhs,long long rhs)
{
    long long lhs2=lhs%100000;
    long long rhs2=rhs%100000;
    return ((lhs/100000*rhs2+rhs/100000*lhs2)*100000+lhs2*rhs2)%MOD;
}

最后贴一个完整的代码：

 

图论 Comments(4) 2010年10月08日 20:29