题目描述

在有向无环图上给你两个起点和终点分别为 $a, b, c, d$。问有几种路径方案使得能从 $a$ 走到 $b$ 的同时能从 $c$ 走到 $d$，且两个路径没有交点。

$1 \le n \le 200, 1 \le m \le 5000$。

---

经过了深刻地思考，你会发现，由于这是一个 $DAG$ 图，我们可以将其转化为动态规划来做，同时我们先要将图建立成一个拓扑图。

然后你又经过了深刻地思考，你会发现这道题还需要容斥原理。

假设 $g[i]$ 是从 $a_1$ 和 $b_1$ 到共同点 $i$ 的路径总方案数，则可以得

$$g[i] = f[a_1][i] * f[b_1][i] - \sum_{k=1}^{i-1} g[k] * f[k][i]^2$$

则可以得

$$ans = f[a_1][b_1] * f[a_2][b_2] - \sum_{k=1}^{n} g[k] * f[k][a_2] * f[k][b_2]$$

由于数据范围较小，知道了思路是个 Oler 都有方法将其实现，不存在卡时间的问题。

#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
const int maxn=205;
struct node
{
    int next,to;
}edge[200005];
int head[200005];
int g[maxn],f[maxn][maxn],in[maxn],pos[maxn];
int n,m,u,v,a,b,c,d,cnt,tot,ans;
queue<int> q;
void add(int from,int to)
{
    edge[++tot].next=head[from];
    edge[tot].to=to;
    head[from]=tot;
    in[to]++;
}
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
signed main()
{
    n=read(),m=read();
    for (int i=1;i<=m;i++)
    {
        u=read(),v=read();
        add(u,v);
    }
    a=read(),b=read(),c=read(),d=read();
    for (int i=1;i<=n;i++) if (!in[i]) q.push(i);
    while(!q.empty())
    {
        int now=q.front();q.pop();
        pos[++cnt]=now;
        for (int i=head[now];i;i=edge[i].next)
        {
            int to=edge[i].to;
            in[to]--;
            if (!in[to]) q.push(to);
        }
    }
    for (int i=1;i<=n;i++)
    {
        u=pos[i];f[u][u]=1;
        for (int j=i;j<=n;j++)
        {
            v=pos[j];
            for (int k=head[v];k;k=edge[k].next){
                int to=edge[k].to;
                f[u][to]+=f[u][v];
            }
        }
    }
    for (int i=1;i<=n;i++)
    {
        u=pos[i];
        g[u]=f[a][u]*f[c][u];
        for (int j=1;j<i;j++)
        {
            v=pos[j];
            g[u]-=g[v]*f[v][u]*f[v][u];
        }
    }
    ans=f[a][b]*f[c][d];
    for (int i=1;i<=n;i++) u=pos[i],ans-=g[u]*f[u][b]*f[u][d];
    printf("%lld",ans);
    return 0;
}