BZOJ1415 [Noi2005]聪聪和可可

最近很颓啊。

这题很久之前看过。当时以为是高消就没管。然后开坑之神idy做了之后仔细一想才知道不是。

这题的做法是dp。首先因为边数少所以不用floyd，直接bfs预处理出所有t[i][j]表狼在i，兔子在j的时候狼下一步去哪。然后有一个结论是每一步两个玩意的距离至少缩短1，所以状态是不会有环的，这也是为啥可以不用高消。然后坑点是不能直接开状态队列，因为那不是拓补序。要先把每个点的入度算出来再跑dp。结局是我的代码超长。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

struct edge {
	int t;
	edge *next;
};

#define mkword(_x_,_y_) (((_x_)<<16)|(_y_))
#define hiword(_x_) ((_x_)>>16)
#define loword(_x_) ((_x_)&0x0000ffff)

const int maxn = 1009;
const int maxst = 1000009;
const int inf = 0x3f3f3f3f;

int n, m, st, te, deg[maxn], d[maxn], t[maxn][maxn], ind[maxn][maxn];
edge elst[maxn << 1], *ep(elst), *head[maxn];
double f[maxn][maxn], g[maxn][maxn], c[maxn], ans;

inline void addEdge(int u, int v) {
	ep-> t = v;
	ep-> next = head[u];
	head[u] = ep ++;
}

void bfs(int p0) {
	static int q[maxn];
	int hd(0), tl(1);
	memset(d, -1, sizeof(d));
	d[q[0] = p0] = 0;
	while (hd < tl) {
		int p(q[hd ++]);
		for (edge* e = head[p]; e; e = e-> next)
			if (d[e-> t] == -1) {
				d[e-> t] = d[p] + 1;
				q[tl ++] = e-> t;
			}
	}
	for (int p = 1; p <= n; ++ p)
		if (p == p0) {
			t[p][p] = p;
		}
		else {
			t[p][p0] = inf;
			for (edge* e = head[p]; e; e = e-> next)
				if (d[p] == d[e-> t] + 1 && e-> t < t[p][p0])
					t[p][p0] = e-> t;
		}
}

void dp() {
	static int q[maxst];
	static bool iq[maxn][maxn];
	int hd(0), tl(1);
	memset(iq, 0, sizeof(iq));
	memset(f, 0, sizeof(f));
	memset(g, 0, sizeof(g));
	memset(ind, 0, sizeof(ind));
	ans = 0;
	q[0] = mkword(st, te);
	iq[st][te] = 1;
	while (hd < tl) {
		int i(hiword(q[hd])), j(loword(q[hd])), i0, j0;
		++ hd;
		if (t[t[i][j]][j] != j) {
			for (edge* e = head[j]; e; e = e-> next) {
				i0 = t[t[i][j]][j];
				j0 = e-> t;
				++ ind[i0][j0];
				int zn(mkword(i0, j0));
				if (!iq[i0][j0]) {
					q[tl ++] = zn;
					iq[i0][j0] = 1;
				}
			}
			i0 = t[t[i][j]][j];
			j0 = j;
			++ ind[i0][j0];
			int zn(mkword(i0, j0));
			if (!iq[i0][j0]) {
				q[tl ++] = zn;
				iq[i0][j0] = 1;
			}
		}
	}
	memset(f, 0, sizeof(f));
	memset(g, 0, sizeof(g));
	g[st][te] = 1;
	ans = 0;
	q[0] = mkword(st, te);
	hd = 0;
	tl = 1;
	while (hd < tl) {
		int i(hiword(q[hd])), j(loword(q[hd])), i0, j0;
		++ hd;
		if (i == j) {
			ans += f[i][j];
		}
		else if (t[t[i][j]][j] == j) {
			ans += f[i][j] + g[i][j];
		}
		else {
			for (edge* e = head[j]; e; e = e-> next) {
				i0 = t[t[i][j]][j];
				j0 = e-> t;
				g[i0][j0] += g[i][j] * c[j];
				f[i0][j0] += (f[i][j] + g[i][j]) * c[j];
				int zn(mkword(i0, j0));
				-- ind[i0][j0];
				if (!ind[i0][j0])
					q[tl ++] = zn;
			}
			i0 = t[t[i][j]][j];
			j0 = j;
			g[i0][j0] += g[i][j] * c[j];
			f[i0][j0] += (f[i][j] + g[i][j]) * c[j];
			int zn(mkword(i0, j0));
			-- ind[i0][j0];
			if (!ind[i0][j0])
				q[tl ++] = zn;
		}
	}
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
#endif

	scanf("%d%d%d%d", &n, &m, &st, &te);
	memset(d, 0x3f, sizeof(d));
	memset(deg, 0, sizeof(deg));
	for (int i = 0; i < m; ++ i) {
		int u, v;
		scanf("%d%d", &u, &v);
		addEdge(u, v);
		addEdge(v, u);
		++ deg[u];
		++ deg[v];
	}
	for (int i = 1; i <= n; ++ i) {
		bfs(i);
		c[i] = 1.0 / (deg[i] + 1);
	}
	dp();
	printf("%.3lf\n", ans);
}