不相交路径¶

题意¶

一个有向无环图，给定四个点 $a, b, c, d$ ，求出有多少对路径 ( $a \rightarrow b, c \rightarrow d$ ) 满足两条路径没有公共点。

解析¶

考虑补集转化，即用所有路径对的总数减去相交的路径对。

设 $f(x, y)$ 为从 $x$ 出发，到达 $y$ 的方案数，而 $g(x)$ 表示满足从 $a$ 出发到达 $x$ ，从 $b$ 出发到达 $x$ 且不相交的路径对数。则答案为全集减去

$\sum_{x=1}^ng(x)f(x,c)f(x,d)$

其中 $f$ 显然可以通过 $O(nm)$ 的 DP 预处理，但 $g$ 却没法直接计算。再进行一次补集转化即可

$g(x)=f(a,x)f(b,x)-\sum_{i<x{\text{ topologically}}}g(i)f(i, x)^2$

实现¶

#include <bits/stdc++.h>

typedef long long int ll;
const int maxn = 159;

struct Edge{
    int to, next;
}edge[maxn * maxn];

int head[maxn];

inline void add(int from, int to){
    edge[++head[0]].to = to;
    edge[head[0]].next = head[from];
    head[from] = head[0];
}

ll f[maxn][maxn], g[maxn];
int q[maxn], h = 1, t;
int n, m, deg[maxn];
int a, b, c, d;

int main(){
    std::scanf("%d%d", &n, &m);
    for(int i = 1, x, y; i <= m; ++i){
        std::scanf("%d%d", &x, &y);
        add(x, y), ++deg[y];
    }
    std::scanf("%d%d%d%d", &a, &b, &c, &d);

    for(int i = 1; i <= n; ++i)
        if(deg[i] == 0)
            q[++t] = i;
    while(h <= t){
        int node = q[h++];
        for(int i = head[node]; i; i = edge[i].next)
            if(--deg[edge[i].to] == 0)
                q[++t] = edge[i].to;
    }

    for(int i = 1; i <= n; ++i){
        int node = q[i];
        f[node][node] = 1;
        for(int j = i; j < n; ++j)
            for(int k = head[q[j]]; k; k = edge[k].next)
                f[node][edge[k].to] += f[node][q[j]];
    }

    for(int i = 1; i <= n; ++i){
        int node = q[i];
        g[node] = f[a][node] * f[c][node];
        for(int j = 1; j < i; ++j)
            g[node] -= g[q[j]] * f[q[j]][node] * f[q[j]][node];
    }

    ll ans = f[a][b] * f[c][d];
    for(int i = 1; i <= n; ++i)
        ans -= g[i] * f[i][b] * f[i][d];

    std::printf("%lld\n", ans);
    return 0;
}

来源¶

BZOJ1471 不相交路径

不相交路径¶

题意¶

解析¶

实现¶

来源¶

评论