Vexoben
Jun 21, 2018
题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=2750
题意
给定一张有向图，对于所有边，求经过这条边的最短路条数。起点终点可以任选。
n<=1500,m<=4000
题解
昨天在床上糊到十一点半……好在今天打完就直接过了。
肯定要枚举点或边。如果枚举边，可以用总最短路条数-删去这条边后的最短条数。我只能糊出O(n^2m*log(m))的做法，并不能通过。
然后考虑枚举起点S。联想到最短路径树，如果我们将所有可能在最短路中出现的边保留，即E’={(x,y)∈E，dist[x]+weight(x,y)=dist[y]},可以获得一张最短路网。这张图中dist小的向dist大的连边，显然是一张DAG。同时可以发现，从S出发沿着任意方向行走，走出的都是以S为起点的最短路。
考虑最短路网中的一条边(x,y)，以S为起点经过(x,y)的最短路，应为(S到x的最短路条数)*(y到其余点的最短路条数)。可以用两个DP分别对所有点处理出这个值。
#include<bits/stdc++.h>
using namespace std;
const int N=1505;
const int M=5005;
const int mod=1e9+7;
int n,m,S,ans[M];
namespace G2 {
int E=0;
int fir[N],nex[M],arr[M],num[M],deg[N],dp1[N],dp2[N];
queue<int> Q;
inline void Init() {
E=0;
memset(fir,0,sizeof(fir));
memset(deg,0,sizeof(deg));
memset(dp1,0,sizeof(dp1));
memset(dp2,0xff,sizeof(dp2));
}
inline void Add_Edge(int x,int y,int p) {
nex[++E]=fir[x];
fir[x]=E; arr[E]=y; num[E]=p; deg[y]++;
}
inline void DP1() {
Q.push(S); dp1[S]=1;
while (!Q.empty()) {
int x=Q.front(); Q.pop();
for (int i=fir[x];i;i=nex[i]) {
dp1[arr[i]]+=dp1[x];
if (dp1[arr[i]]>=mod) dp1[arr[i]]-=mod;
if (--deg[arr[i]]==0) Q.push(arr[i]);
}
}
}
inline int DP2(int x) {
if (~dp2[x]) return dp2[x];
dp2[x]=1;
for (int i=fir[x];i;i=nex[i]) {
dp2[x]+=DP2(arr[i]);
if (dp2[x]>=mod) dp2[x]-=mod;
}
return dp2[x];
}
inline void Solve() {
DP1(); DP2(S);
for (int i=1;i<=n;i++) {
for (int j=fir[i];j;j=nex[j]) {
ans[num[j]]+=1LL*dp1[i]*dp2[arr[j]]%mod;
if (ans[num[j]]>=mod) ans[num[j]]-=mod;
}
}
}
}
namespace G1 {
int E=0;
int fir[N],nex[M],arr[M],len[M],dis[N],vis[N];
queue<int> Q;
inline void Add_Edge(int x,int y,int l) {
nex[++E]=fir[x];
fir[x]=E; arr[E]=y; len[E]=l;
}
inline void Spfa() {
memset(dis,0x3f,sizeof(dis));
dis[S]=0; Q.push(S);
while (!Q.empty()) {
int x=Q.front(); Q.pop(); vis[x]=0;
for (int i=fir[x];i;i=nex[i]) {
if (dis[arr[i]]<=dis[x]+len[i]) continue;
dis[arr[i]]=dis[x]+len[i];
if (!vis[arr[i]]) vis[arr[i]]=1,Q.push(arr[i]);
}
}
}
inline void Calc() {
G2::Init();
for (int i=1;i<=n;i++) {
for (int j=fir[i];j;j=nex[j]) {
if (dis[i]+len[j]!=dis[arr[j]]) continue;
G2::Add_Edge(i,arr[j],j);
}
}
G2::Solve();
}
}
int main() {
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++) {
int x,y,l; scanf("%d%d%d",&x,&y,&l);
G1::Add_Edge(x,y,l);
}
for (S=1;S<=n;S++) {
G1::Spfa(); G1::Calc();
}
for (int i=1;i<=m;i++) printf("%d\n",ans[i]);
return 0;
}