不相交路径[BZOJ1471] 容斥原理 拓扑排序
最近学容斥的时候又碰到一道类似的题目,所以想分享一个套路,拿这题来举例
【题目描述】
给出一个\(N(N\leq 150)\)个结点的有向无环简单图。给出4个不同的点\(a,b,c,d\),定义不相交路径为两条路径,两条路径的起点分别为\(a\)和\(c\),对应的两条路径的终点为\(b\)和\(d\),要求满足这两条路径不相交,即两条路径上没有公共的点。 现在要求不相交路径的方案数。
【输入格式】
第一行为\(N,M\)。表示这个有向无环图有\(N\)个节点,\(M\)条边。 接下来\(M\)行,每行两个整数\(x,y\)。表示\(x\)至\(y\)有一条有向边。 接下来一行四个数\(a,b,c,d\),意义如题中所述。
【输出格式】
输出为一行,即答案(方案数)。
在写这题之前,先看另外一个问题:
一个\(N*M(N, M \le 100000)\)的矩阵,从\((0,0)\)出发,每次可以向上或者向右走一步,问有多少种方案到达点\((N,M)\)?
很显然,答案是\(C^N_{N*M}\)。
那如果规定有\(K\)个点是不能走的呢?\((k \le 1000)\)
如果直接递推的话肯定是会超时的 所以我们要使用一些数学方法
具体来说,合法方案数等于总方案数减去不合法方案数 废话
如果直接对于每个不合法点有多少路径经过它,然后用总数减去这些方案的话,很有可能会重复删减同一个方案,因为一种方案可能经过多个不合法点。
所以我们改变一下思路,设\(f[i]\)表示有多少路径第一个经过的不合法点为\(i\),最后用总方案数减去所有的\(f[i]\)。由于一条不合法路径无论如何都只会有一个【第一个经过的不合法点】,所以这种方法显然是正确的。
统计时,只需将所有不合法点先按照\(X,Y\)轴大小排好序,对于一个不合法点\(i\),\(f[i] = (\)从\((0,0)\)到\(i\)点的方案数 $- \sum f[j]) * \(从\)i\(点到\)(N,M)\(的方案数,其中\)j$是所有位于它左下方的点。
时间复杂度 \(O(k^2)\),这就是数学的力♂量
再看此题,类似的,我们可以设\(f[i]\)表示第一次相交在\(i\)点的情况数。
先用\(DP, Floyd\),等各种奇葩方法求出任意两点\(u, v\)从\(u\)到\(v\)的路径数。
然后按照拓扑序算出每个\(f[i]\),\(f[i] = (cnt[a][i] * cnt[b][i] – \sum f[j] * cnt[j][i]^2) * cnt[i][c] * cnt[i][d]\),\(j\)为每个拓扑序在\(i\)之前的点。
答案\(=\)总方案数 \(- \sum f[i]\)
【代码】
#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;
}