luogu4061 大吉大利 晚上吃鸡！

链接

最短路径\(dag\)，一道好题。题目大意：求一张图中满足下列要求的点对\((i,j)\)数量：所有最短路径必定会经过 \(i\) 点和 \(j\) 点中的任意一点。不存在一条最短路同时经过 \(i\) 点和 \(j\) 点。考虑这两个限制是啥。首先所有最短路要么经过\(i\)点，要么经过\(j\)点，不存在两个都不经过或者都经过的。所以经过\(i\)点的最短路方案加上经过\(j\)点的最短路方案不存在交集。那么考虑怎么求最短路方案，先做一边\(dij\)，然后在\(tag\)上\(dp\)方案数即可，正反都做一遍。那么有\(f_{i,0}\)表示从\(s\)到\(i\)正向最短路方案数，经过\(i\)点的最短路方案设为\(F_{i}\)，有\[{F_{i}=f_{i,0}*f_{i,1}}\]所以满足要求的\(i,j\)可写为：\[F_i+F_j=F_t\]。这个满足了还不够，因为这个只是\(i,j\)的必要条件，还不是充分条件。关键在于所有的路径不能同时经过这两个点。设\(G_{i,0}\)表示从\(s\)点到\(i\)点可能经过的点集，\(bitset\)实现，\(G_{i,1}\)同理。转移拓扑排序实现即可。所以我们对于每一个\(i\)，想知道\(F_{t}-F_{i}=F_{j}\)中，\(j\)的点数，减去\(i\)可以到达的点数。维护一个\(map\)，记录\(F_{j}\)这个集合中的点。那么对于一个\(i\)，他能产生的贡献就是集合\[S=G_{F_t-F_i}\ and\ G_{i,0}\ and \ G_{i,1}\]的\(1\)的个数。空间\(1GB\)就可以过

// luogu-judger-enable-o2#include<bits/stdc++.h>#define R register int#define ll long long using namespace std;const int N=50001;const int M=100001;const ll inf=1e18;const int mod=1000000009;int n,m,s,u,v,x,t,ans,vis[N];int cnt,nt[M],to[M],hd[N],w[M];int du[N];ll Dis[2][N],f[2][N],F[N];void link(R f,R t,R d){nt[++cnt]=hd[f],to[cnt]=t,w[cnt]=x,hd[f]=cnt;}bitset<50001>G[2][N];map<ll,bitset<50001> >Ms;int gi(){R x=0,k=1;char c=getchar();while((c<'0'||c>'9')&&c!='-')c=getchar();if(c=='-')k=-1,c=getchar();while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();return x*k;}struct ip{int id;ll val;};int operator < (ip x,ip y){return x.val>y.val;}priority_queue<ip>Q;void dij(R op){while(!Q.empty())Q.pop();for(R i=1;i<=n;++i)vis[i]=0,Dis[op][i]=inf;if(op)Dis[1][t]=0,Q.push((ip){t,0}),f[op][t]=1;else Dis[0][s]=0,Q.push((ip){s,0}),f[op][s]=1;while(!Q.empty()){ip s=Q.top();Q.pop();if(vis[s.id])continue;R i=s.id;vis[i]=1;for(R k=hd[i];k;k=nt[k]){if(Dis[op][to[k]]>Dis[op][i]+w[k]){Dis[op][to[k]]=Dis[op][i]+w[k];f[op][to[k]]=f[op][i],Q.push((ip){to[k],Dis[op][to[k]]});}else if(Dis[op][to[k]]==Dis[op][i]+w[k])f[op][to[k]]+=f[op][i];}}}queue<int>til;void top(R op){for(R i=1;i<=n;++i)for(R k=hd[i];k;k=nt[k])if(Dis[op][i]+w[k]+Dis[!op][to[k]]==Dis[0][t])du[to[k]]++;for(R i=1;i<=n;++i){G[op][i].set(),G[op][i][0]=G[op][i][i]=0;if(!du[i])til.push(i);}while(!til.empty()){R i=til.front();til.pop();for(R k=hd[i];k;k=nt[k])if(Dis[op][i]+w[k]+Dis[!op][to[k]]==Dis[0][t]){du[to[k]]--,G[op][to[k]]&=G[op][i];if(!du[k])til.push(to[k]);}}}int main(){n=gi(),m=gi(),s=gi(),t=gi();for(R i=1;i<=m;++i)u=gi(),v=gi(),x=gi(),link(u,v,x),link(v,u,x);dij(0),dij(1);if(!f[0][t])return printf("%lld",1ll*n*(n-1)/2),0;for(R i=1;i<=n;++i)if(Dis[0][i]+Dis[1][i]==Dis[0][t])F[i]=f[0][i]*f[1][i];top(0),top(1);for(R i=1;i<=n;++i)Ms[F[i]].set(i);for(R i=1;i<=n;++i)ans+=(Ms[F[t]-F[i]]&G[0][i]&G[1][i]).count();cout<<(ans>>1);return 0;}

如果觉得《luogu4061 大吉大利 晚上吃鸡！》对你有帮助，请点赞、收藏，并留下你的观点哦！