不相交路径[BZOJ1471]

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;

ll n, m, a, b, c, d, ans;
ll x[505][505], in[505], f[505][505], g[505];
ll que[5005], head = 1, tail;

void toposort() {
	for (int i = 1; i <= n; i++) {
		if (in[i] == 0) que[++tail] = i, in[i] = -1;
	}
	while (head <= tail) {
		ll c = que[head];
		head++;
		for (int i = 1; i <= n; i++) {
			if (x[c][i]) {
				in[i]--;
				if (in[i] == 0) que[++tail] = i, in[i] = -1;
			}
		}
	}
}

int main() {
	scanf("%lld %lld", &n, &m);
	for (int i = 1; i <= m; i++) {
		ll xx, yy;
		scanf("%lld %lld", &xx, &yy);
		x[xx][yy] = f[xx][yy] = 1;
		in[yy]++;
	}
	scanf("%lld %lld %lld %lld", &a, &b, &c, &d);
	toposort();
	for (int i = 1; i <= n; i++) f[i][i] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			ll u = que[i], v = que[j];
			for (int k = 1; k <= n; k++) {
				if (x[v][k]) {
					f[u][k] += f[u][v];
				}
			}
		}
	}
	ans = f[a][b] * f[c][d];
	for (int i = 1; i <= n; i++) {
		ll cur = que[i];
		g[cur] = f[a][cur] * f[c][cur];
		for (int j = i - 1; j >= 1; j--){
			g[cur] -= g[que[j]] * f[que[j]][cur] * f[que[j]][cur];
		} 
		ans -= g[cur] * f[cur][b] * f[cur][d];
	}
	printf("%lld\n", ans);
	return 0;
}