nssl 1471.Y

$Description$

一张无向图，每条边的权值分为0和1，问有多少条从1出发，长度为 $d$的不同的01串

数据范围： $n\leq 90,d\leq 20$

$Solution$

很容易写出一种 $dp$，设 $f[i][j][S]$表示 $i$开始 $j$结束的状态为 $S$的路径是否存在

然后这样时间空间貌似都有点问题

于是考虑折半搜，把这个拆成两部分：

$f[S][i]$表示状态为 $S$，从 $i$出发可以到达的点【二进制状压】
$g[S][i]$表示状态为 $S$，从某个点出发可以到达的点【二进制状压】（这个点未知，是你在求 $f$的过程中顺便求的）

酱紫时间还是慢了点，开个 $bitset$优化常数就可以过了

然后枚举状态计算即可，恶心的地方在于位运算（艹）

$Code$

#include<cstdio>
#include<cctype>
#include<bitset> 
#define LL long long
using namespace std;int n,m,d,x,y,ans;
bitset<100>a[100],b[100],f[1<<11],g[1<<11];
bool k;
inline LL read()
{char c;LL d=1,f=0;while(c=getchar(),!isdigit(c)) if(c=='-') d=-1;f=(f<<3)+(f<<1)+c-48;while(c=getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48;return d*f;
}
signed main()
{n=read();m=read();d=read();for(register int i=1;i<=m;i++) {x=read();y=read();k=read();if(k==0) a[x][y]=a[y][x]=1;if(k==1) b[x][y]=b[y][x]=1;}int d2=d/2,d1=d-d2;for(register int i=n;i>0;i--){for(register int s=0;s<(1<<11);s++) f[s].reset();f[1][i]=1;for(register int s=1;s<(1<<d1);s++)for(register int j=1;j<=n;j++)if(f[s][j]!=0){f[s<<1]|=a[j];f[s<<1|1]|=b[j];}for(register int s=0;s<(1<<d1);s++)g[s][i]=f[1<<d1|s].any();}for(register int i=0;i<(1<<d1);i++)for(register int j=0;j<(1<<d2);j++)if((g[i]&f[1<<d2|j]).any()) ans++;printf("%d",ans);
}