HDU2433 travel (最短路径树)

题面如图

分析

直接做的复杂度是 $O(n\ast m\ast m)$O(n∗m∗m)，问题在于每割一条边对每个点都要做一次最短路，而其实某些点的最短路并没有发生变化。
于是我们有一个优化的思路：
如果这条边不在某些点为出发点的最短路上，显然不用从这个点跑一次最短路；如果在的话就跑一次最短路

如何实现这个操作呢？
我们先可以先处理出每一个点出发的最短路路径（由于边长是 $1$1，于是用 $bfs$bfs 即可），这其实是一颗以 $a$a 为顶点的生成树（如果最短路有多种方案，只记一种）。用 $u\left[a\right]\left[b\right]\left[c\right]$u[a][b][c] 表示 $b\to c$b→c 这条边是否在 $a$a 为顶点的生成树上。每次枚举边的时候判断一下，如果在以 $i$i 为根的生成树上，就跑一次最短路。

思考一下复杂度？
有 $n$n 棵树， 一棵树只有 $n-1$n−1 条边，也就是说在树上的边数为
min(n∗(n−1),3000)<3000，所以最多跑 $3000$3000 次最短路，每次最短路是 $O\left(m\right)$O(m) 的，所以总复杂度是 $O(m\ast m)$O(m∗m)

代码如下

#include <bits/stdc++.h>
#define N 105
#define M 3005
#define inf 2147483647
using namespace std;
struct node{
	int a, b, c, n;
	bool operator < (const node & A) const{
		return c > A.c;	
	}
}d[M * 2];
int h[N], cnt, dis[N], s[N], t[N], n, m, v[M * 2], ret[N][N], u[N][N][N], flag;
void cr(int a, int b, int c){
	d[++cnt].a = a; d[cnt].b = b; d[cnt].c = c; d[cnt].n = h[a]; h[a] = cnt;
}
void bfs(int x, int p){
	int i, a, b;
	if(!p) memset(u[x], 0, sizeof(u[x]));
	s[x] = 0;
	queue<int> q;
	q.push(x);
	memset(dis, -1, sizeof(dis));
	dis[x] = 0;
	while(!q.empty()){
		a = q.front(); q.pop();
		for(i = h[a]; i; i = d[i].n){
			if(v[i]) continue;
			b = d[i].b;
			if(dis[b] > -1) continue;
			dis[b] = dis[a] + 1;
			if(!p) u[x][a][b] = u[x][b][a] = 1;
			q.push(b);
		}
	}
	for(i = 1; i <= n; i++){
		if(dis[i] == -1) flag = 1;
		s[x] += dis[i];
	}
}
int main(){
	int i, j, k, a, b, sum;
	while(scanf("%d%d", &n, &m) != EOF){
		memset(h, 0, sizeof(h));
		memset(ret, 0, sizeof(ret));
		cnt = flag = sum = 0;
		for(i = 1; i <= m; i++){
			scanf("%d%d", &a, &b);
			cr(a, b, 1);
			cr(b, a, 1);
			ret[a][b]++;
			ret[b][a]++;
		}
		for(i = 1; i <= n; i++) bfs(i, 0), t[i] = s[i];
		if(flag){
			for(i = 1; i <= m; i++) printf("INF\n");
			continue;
		}
		for(i = 1; i <= cnt; i += 2){
			flag = sum = 0;
			a = d[i].a; b = d[i].b;
			v[i] = v[i + 1] = 1;
			for(j = 1; j <= n; j++){
				if(!u[j][a][b] || ret[a][b] > 1) sum += t[j];
				else{
					//printf("%d %d %d===\n", j, a, b);
					bfs(j, 1);
					sum += s[j];
					if(flag) break;
				}
			}
			if(flag) printf("INF\n");
			else printf("%d\n", sum);
			v[i] = v[i + 1] = 0;
		}
	}
	return 0;
}