AT_abc041_d [ABC041D] 徒競走 题解

23 年 8 月 5 日 星期六
127 字
1 分钟

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

思路/解析

状压 dp。

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

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

代码

cpp
#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];
}

文章标题：AT_abc041_d [ABC041D] 徒競走 题解

文章作者：Walter_Fang

文章链接：https://blog.walterfang.us.kg/posts/solution-at_abc041_d[复制]

最后修改时间：

商业转载请联系站长获得授权，非商业转载请注明本文出处及文章链接，您可以自由地在任何媒体以任何形式复制和分发作品，也可以修改和创作，但是分发衍生作品时必须采用相同的许可协议。
本文采用CC BY-NC-SA 4.0进行许可。