ZOJ 3408 Gao

zoj题目页面传送门

给定一个有向图\(g=(v,e),n=|v|,m=|e|\)（可能有重边和自环，节点从\(0\)开始编号），以及\(q\)组询问，对于每组询问你需要回答有多少条从节点\(0\)开始的最短路经过节点\(x\)（节点\(0\)到某一个节点的最短路可能不唯一），输出答案的后\(10\)位。本题多测。

\(q,n\in[1,10^4],m\in[1,5\times10^4]\)，边权为正。

既然题目要数最短路的个数，我们可以把那些不在最短路上的边去掉，只保留在最短路上的边，构造出一个新图\(g'=(v,e')\)。这样问题就转化成了在\(\bm {g'}\)上有多少条从节点\(\bm0\)开始的路径经过节点\(\bm x\)（显然的吧）。那怎么知道那些边该留那些边不该留呢？我们可以先跑一边堆优化dijkstra求出到节点\(0\)的最短路长度数组\(dis\)，那么\(e'=\{(x,y,len)|(x,y,len)\in e,dis_y=dis_x+len\}\)。

接下来我们就要求在\(\bm {g'}\)上有多少条从节点\(\bm0\)开始的路径经过节点\(\bm x\)了。我们考虑将一条从节点\(0\)开始、经过节点\(x\)、终点为\(y\)的路径拆成两段：\(0\to x,x\to y\)，对它们分别计数，最后相乘即可。很显然，\(g'\)是无环的，也就是一个dag（因为边权为正），这样就可以在\(g'\)上dp了。设\(dp1_i\)表示路径\(0\to i\)的个数，\(dp2_i\)表示以\(i\)为起点的路径（即\(\sum\limits_{j\in v}\text{路径}i\to j\text{的个数}\)）。状态转移方程显然是：

\[ \begin{aligned} dp1_i&=\begin{cases}1&i=0\\\sum\limits_{(j,i,len)\in e'}dp1_j&i>0\end{cases}\\ dp2_i&=\sum_{(i,j,len)\in e'}dp2_j+1 \end{aligned} \]

可这是一个图啊，dp顺序是什么呢？容易发现，要想知道\(dp1_i\)，得先知道\(\forall j\left((j,i,len)\in e'\right)\)，所以要按照拓扑序dp；\(dp2\)反之，要按照拓扑逆序dp。（如果你懒得写拓扑排序，也可以记忆化搜索）

这题还有个毒瘤的地方，就是要保留后\(10\)位（即\(\bmod 10^{10}\)），在乘法的时候会到\(10^{20}\)，爆unsigned long long。这时聪明（ruì zhì）的读者可能会写高精度（毕竟只有最后一步才是乘法，不会tle），但有个更巧妙的方法：利用乘法分配律，显然

\[xy\bmod10^{10}=\left(\left(10^5\left\lfloor\dfrac x{10^5}\right\rfloor+x\bmod10^5\right)\left(10^5\left\lfloor\dfrac y{10^5}\right\rfloor+y\bmod10^5\right)\right)\bmod10^{10}=\left(10^{10}\left\lfloor\dfrac x{10^5}\right\rfloor\left\lfloor\dfrac y{10^5}\right\rfloor+10^5\left\lfloor\dfrac x{10^5}\right\rfloor\left(y\bmod10^5\right)+10^5\left(x\bmod10^5\right)\left\lfloor\dfrac y{10^5}\right\rfloor+\left(x\bmod10^5\right)\left(y\bmod10^5\right)\right)\bmod10^{10}=\left(\left(10^5\left\lfloor\dfrac x{10^5}\right\rfloor\right)\left(y\bmod10^5\right)+\left(x\bmod10^5\right)\left(10^5\left\lfloor\dfrac y{10^5}\right\rfloor\right)+\left(x\bmod10^5\right)\left(y\bmod10^5\right)\right)\bmod10^{10}=\left(\left(x\bmod10^5\right)y+\left(10^5\left\lfloor\dfrac x{10^5}\right\rfloor\right)\left(y\bmod10^5\right)\right)\bmod10^{10} \]

这样最大是\(10^5\times10^{10}=10^{15}\)级别的，不会爆。

下面贴ac代码：（最近码风有了很大的改变）

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mp make_pair
#define x first
#define y second
#define pb push_back
const int mod=10000000000ll,inf=1e18;
const int n=10000;
int n/*点数*/,m/*边数*/,qu/*数据组数*/;
vector<pair<int,int> > nei[n]/*原邻接表*/;
vector<int> dnei[n]/*新邻接表*/,rnei[n]/*新反邻接表*/;
int dis[n]/*到节点0的最短路长度*/;
bool vis[n]/*访问标记*/;
int ideg[n]/*新图中的入度*/;
void dijkstra(){//堆优化dijkstra
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
    q.push(mp(0,0));
    for(int i=1;i<n;i++)dis[i]=inf;
    for(int i=0;i<n;i++)vis[i]=false;
    while(q.size()){
        int x=q.top().y;
        q.pop();
        if(vis[x])continue;
        vis[x]=true;
        for(int i=0;i<nei[x].size();i++){
            int y=nei[x][i].x,len=nei[x][i].y;
            if(dis[x]+len<dis[y])q.push(mp(dis[y]=dis[x]+len,y));
        }
    }
    //建新图
    for(int i=0;i<n;i++)dnei[i].clear(),rnei[i].clear();
    for(int i=0;i<n;i++)for(int j=0;j<nei[i].size();j++){
        int x=nei[i][j].x,len=nei[i][j].y;
        if(dis[x]==dis[i]+len)dnei[i].pb(x),rnei[x].pb(i),ideg[x]++;
    }
}
vector<int> topo;//拓扑序
void toposort(){//拓扑排序
    queue<int> q;
    for(int i=0;i<n;i++)if(!ideg[i])q.push(i);
    topo.clear();
    while(q.size()){
        int x=q.front();
        q.pop();
        topo.pb(x);
        for(int i=0;i<dnei[x].size();i++){
            int y=dnei[x][i];
            ideg[y]--;
            if(!ideg[y])q.push(y);
        }
    }
}
int dp1[n]/*dp1[i]表示新图中路径0->i的个数*/,dp2[n]/*dp2[i]表示新图中路径i->j的个数之和*/;
int prod(int x,int y){//mod 10^5意义下的乘法
    int lx=x%100000,ly=y%100000;
    return (lx*y+(x-lx)*ly)%mod;
}
void prt(int x){//输出后10位
    vector<int> v;
    for(int i=1;i<=10;i++)v.pb(x%10),x/=10;
    for(int i=9;~i;i--)printf("%lld",v[i]);
}
void mian(){
    for(int i=0;i<n;i++)nei[i].clear();
    while(m--){
        int x,y,z;
        scanf("%lld%lld%lld",&x,&y,&z);
        nei[x].pb(mp(y,z));
    }
    dijkstra();
    toposort();
    for(int i=0;i<n;i++){//dp1，拓扑序
        int x=topo[i];
        dp1[x]=!x;
        for(int j=0;j<rnei[x].size();j++)
            (dp1[x]+=dp1[rnei[x][j]])%=mod;
    }
    for(int i=n-1;~i;i--){//dp2，拓扑逆序
        int x=topo[i];
        dp2[x]=1;
        for(int j=0;j<dnei[x].size();j++)
            (dp2[x]+=dp2[dnei[x][j]])%=mod;
    }
    while(qu--){
        int x;
        scanf("%lld",&x);
        prt(prod(dp1[x],dp2[x]));/*相乘得到总数*/puts("");
    }
}
signed main(){
//  freopen("c:\\users\\chenx\\onedrive\\桌面\\txt.txt","r",stdin);
    while(~scanf("%lld%lld%lld",&n,&m,&qu))mian();
    return 0;
}

我做这题的时候打错了一个字母，把prod(int,int)函数里的ly=y%100000打成了ly=x%100000，导致我调了几个小时。。。哎，血的教训！