AT_abc041_d [ABC041D] 徒競走 题解

· · 题解

翻译已经非常言简意赅了，题目大意就不说了。

思路/解析

状压 dp。

我们用 f_i 保存已经遍历过的点集为 i 的方案数量，那么当要加入一个新节点 j 时，节点 j 的所有子节点必须全部在点集 i 中。

需要注意的是，最初我们将没有点权看作第一种方案，即 f_0=1。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2e5+10;
ll n,m,x,y,i,j,a[N],f[N]={1};
int main(){
    cin>>n>>m;
    for(i=1;i<=m;i++)cin>>x>>y,a[x]|=1<<y-1;
    for(i=0;i<(1<<n);i++)
        for(j=1;j<=n;j++)
            if((a[j]&i)==a[j]&&!(i>>j-1&1))
                f[i|(1<<j-1)]+=f[i];
    cout<<f[(1<<n)-1];
}