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
,导致我调了几个小时。。。哎,血的教训!
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/602388.html