c/c++语言开发共享ZOJ 3408 Gao

zoj题目页面传送门

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

(q,nin[1,10^4],min[1,5times10^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)的路径拆成两段：(0to x,xto y)，对它们分别计数，最后相乘即可。很显然，(g')是无环的，也就是一个dag（因为边权为正），这样就可以在(g')上dp了。设(dp1_i)表示路径(0to i)的个数，(dp2_i)表示以(i)为起点的路径（即(sumlimits_{jin v}text{路径}ito jtext{的个数})）。状态转移方程显然是：

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

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

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

[xybmod10^{10}=left(left(10^5leftlfloordfrac x{10^5}rightrfloor+xbmod10^5right)left(10^5leftlfloordfrac y{10^5}rightrfloor+ybmod10^5right)right)bmod10^{10}=left(10^{10}leftlfloordfrac x{10^5}rightrfloorleftlfloordfrac y{10^5}rightrfloor+10^5leftlfloordfrac x{10^5}rightrfloorleft(ybmod10^5right)+10^5left(xbmod10^5right)leftlfloordfrac y{10^5}rightrfloor+left(xbmod10^5right)left(ybmod10^5right)right)bmod10^{10}=left(left(10^5leftlfloordfrac x{10^5}rightrfloorright)left(ybmod10^5right)+left(xbmod10^5right)left(10^5leftlfloordfrac y{10^5}rightrfloorright)+left(xbmod10^5right)left(ybmod10^5right)right)bmod10^{10}=left(left(xbmod10^5right)y+left(10^5leftlfloordfrac x{10^5}rightrfloorright)left(ybmod10^5right)right)bmod10^{10} ]

这样最大是(10^5times10^{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，导致我调了几个小时。。。哎，血的教训！