题目大意

给出一个 \(n\) 个点 \(m\) 条边的有向图，问每一条边在多少个最短路径中出现。

\(n\le 1500,m\le 5000\)

思路

算我孤陋寡闻了。。。

很显然，我们需要枚举一个起点 \(s\)，然后跑一遍最短路，对于一条边 \((u,v,w)\)，如果存在 \(\text{dist}(u)+w=\text{dist}(v)\)，可以想到 \((u,v)\) 一定会产生答案，我们定义此类边叫做“最短路径图上的边”，它们构成的图叫做“最短路径图”。它有以下两个性质：

\(u\to v\) 的最短路径上的子路径 \(a\to b\) 也是最短路径
最短路径图上不存在环

证明：

因为如果有环的话与最短路径图上的边的定义矛盾了，所以显然。

然后根据性质1我们就可以观察到我们可以在这个图上做 topo 排序，求出到 \(u\) 的最短路径数，\(v\) 到其它点的最短路径数，相乘即是答案。

时间复杂度 \(\Theta(VE)\)，但是用 SPFA 的话还是可以跑很快的。

\(\texttt{Code}\)

#include <bits/stdc++.h>

using namespace std;

#define Int register int

#define mod 1000000007

#define MAXN 5005

template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}

template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}

template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}

bool vis[MAXN],ins[MAXN];

int n,m,toop,st[MAXN],to[MAXN],wei[MAXN],nxt[MAXN],head[MAXN],dist[MAXN];

void Add_Edge (int u,int v,int w){

	to[++ toop] = v,st[toop] = u,wei[toop] = w,nxt[toop] = head[u],head[u] = toop;

}

void SPFA (int s){

	queue <int> q;

	while (!q.empty()) q.pop ();

	memset (vis,0,sizeof (vis));

	memset (dist,0x7f,sizeof (dist));

	dist[s] = 0,vis[s] = 1,q.push (s);

	while (!q.empty()){

		int u = q.front();q.pop ();vis[u] = 0;

		for (Int i = head[u];i;i = nxt[i]){

			int v = to[i],w = wei[i];

			if (dist[v] > dist[u] + w){

				dist[v] = dist[u] + w;

				if (!vis[v]) vis[v] = 1,q.push (v);

			}

		}

	}

	for (Int i = 1;i <= m;++ i) if (dist[to[i]] == dist[st[i]] + wei[i]) ins[i] = 1;else ins[i] = 0;

}

int que[MAXN],deg[MAXN],ans[MAXN],cnt1[MAXN],cnt2[MAXN];

void Topo (int S){

	memset (deg,0,sizeof (deg));

	memset (cnt1,0,sizeof (cnt1));

	memset (cnt2,0,sizeof (cnt2));

	int tot = 0;cnt1[S] = 1;

	for (Int i = 1;i <= m;++ i) if (ins[i]) deg[to[i]] ++;

	queue <int> q;while (!q.empty()) q.pop();q.push (S);

	while (!q.empty()){

		int u = q.front();q.pop (),que[++ tot] = u;

		for (Int i = head[u];i;i = nxt[i]){

			if (!ins[i]) continue;

			(cnt1[to[i]] += cnt1[u]) %= mod;

			if (!(-- deg[to[i]])) q.push (to[i]);

		}

	}

	for (Int k = tot;k >= 1;-- k){

		int u = que[k];cnt2[u] ++;

		for (Int i = head[u];i;i = nxt[i]){

			if (!ins[i]) continue;

			(cnt2[u] += cnt2[to[i]]) %= mod;

		}

	}

}

void Solve (int S){

	SPFA (S),Topo (S);

	for (Int i = 1;i <= m;++ i) if (ins[i]) (ans[i] += 1ll * cnt1[st[i]] * cnt2[to[i]] % mod) %= mod;

}

signed main(){

	read (n,m);

	for (Int i = 1,u,v,w;i <= m;++ i) read (u,v,w),Add_Edge (u,v,w);

	for (Int S = 1;S <= n;++ S) Solve (S);

	for (Int i = 1;i <= m;++ i) write (ans[i]),putchar ('\n');

	return 0;

}

巴特西

题解 [HAOI2012]道路

题目大意

思路

\(\texttt{Code}\)

最新文章

热门文章