[bzoj 1471] 不相交路径 (容斥原理)

题目描述

给出一个$N(n<=150)$个结点的有向无环简单图。给出$4$个不同的点$a$，$b$，$c$，$d$，定义不相交路径为两条路径，两条路径的起点分别为$a$和$c$，对应的两条路径的终点为$b$和$d$，要求满足这两条路径不相交，即两条路径上没有公共的点。 现在要求不相交路径的方案数。

题目分析

这道题类似于[bzoj 4767] 两双手
记$f[i][j]$表示从$i$走到$j$路径条数
$g[i]$表示两个点从$a,c$开始走第一次相遇在i点的方案数
根据容斥常识,则有:
$g[i]=f[a][i]*f[c][i]-sum_{j的拓扑序<i的拓扑序}g[j]*f[j][i]^2$
求最终答案也容斥一下:
$Ans=f[a][b]*f[c][d]-sum g[i]*f[i][b]*f[i][d]$
所以$Theta(n^3)$预处理$f$
所以$Theta(n^2)$求出$g$
所以$Theta(n)$求出$Ans$
时间复杂度$Theta(n^3)$

upd:法2：高论

• 考虑这两个位置第⼀次相交在u，那么可以a->u->c, b->u->d变成 b->u->c, a->u->d。
  所以答案为dp[a][c]*dp[b][d]-dp[b][c]*dp[a][d]

类似LGV Lemma 但是并不满足“一定相交”条件，这里的正确性是两条路径的特殊性导致的。

AC code

法1：100ms

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 155;
int n, m, d[MAXN], fir[MAXN], to[MAXN*MAXN], nxt[MAXN*MAXN], cnt;
inline void Add(int u, int v) { to[++cnt] = v, nxt[cnt] = fir[u], fir[u] = cnt, ++d[v]; }
int topo[MAXN], id[MAXN], cur, q[MAXN], s, t; //topo为拓扑序，id为topo的反函数
long long f[MAXN][MAXN], g[MAXN];
int main ()
{
	scanf("%d%d", &n, &m);
	for(int i = 1, x, y; i <= m; ++i)
		scanf("%d%d", &x, &y), Add(x, y);
	for(int i = 1; i <= n; ++i) if(!d[i]) q[t++] = i;
	while(s < t) //拓扑排序
	{
		int u = q[s++]; id[topo[u] = ++cur] = u;
		for(int i = fir[u]; i; i = nxt[i])
			if(--d[to[i]] == 0) q[t++] = to[i];
	}
	for(int i = 1, u; i <= n; ++i)
	{
		u = id[i]; f[u][u] = 1;
		for(int j = i, v; j <= n; ++j)
		{
			v = id[j];
			for(int k = fir[v]; k; k = nxt[k]) f[u][to[k]] += f[u][v];
		}
	}
	int a, b, c, d;
	scanf("%d%d%d%d", &a, &b, &c, &d);
	for(int i = 1, u; i <= n; ++i)
	{
		u = id[i];
		g[u] = f[a][u] * f[c][u];
		for(int j = 1, v; j < i; ++j)
		{
			v = id[j];
			g[u] -= g[v] * f[v][u] * f[v][u];
		}
	}
	long long ans = f[a][b] * f[c][d];
	for(int i = 1, u; i <= n; ++i)
	{
		u = id[i];
		ans -= g[u] * f[u][b] * f[u][d];
	}
	printf("%lld
", ans);
}

法2：80ms

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 155;
int n, m, d[MAXN], fir[MAXN], to[MAXN*MAXN], nxt[MAXN*MAXN], cnt;
inline void Add(int u, int v) { to[++cnt] = v, nxt[cnt] = fir[u], fir[u] = cnt, ++d[v]; }
int topo[MAXN], id[MAXN], cur, q[MAXN], s, t; //topo为拓扑序，id为topo的反函数
long long f[MAXN][MAXN];
int main ()
{
	scanf("%d%d", &n, &m);
	for(int i = 1, x, y; i <= m; ++i)
		scanf("%d%d", &x, &y), Add(x, y);
	for(int i = 1; i <= n; ++i) if(!d[i]) q[t++] = i;
	while(s < t) //拓扑排序
	{
		int u = q[s++]; id[topo[u] = ++cur] = u;
		for(int i = fir[u]; i; i = nxt[i])
			if(--d[to[i]] == 0) q[t++] = to[i];
	}
	for(int i = 1, u; i <= n; ++i)
	{
		u = id[i]; f[u][u] = 1;
		for(int j = i, v; j <= n; ++j)
		{
			v = id[j];
			for(int k = fir[v]; k; k = nxt[k]) f[u][to[k]] += f[u][v];
		}
	}
	int a, b, c, d;
	scanf("%d%d%d%d", &a, &b, &c, &d);
	long long ans = f[a][b] * f[c][d] - f[c][b] * f[a][d];
	printf("%lld
", ans);
}