【2018-国庆雅礼-NOIP-培训】-D4T2-y

发表于

题解

看到数据范围后便知道搜索必定爆炸，那就只好用动规了

$f[i][j][mask]$ 表示从 $i$ 出发，$j$ 结束，是否存在一条表示为 $mask$ 的路径。 但我们发现还是会超时。

于是我们进行二分（果然二分超级实用的说）————对于每种可能的路径，枚举中间的那个位置判断。时间复杂度为 $O(2^{\frac d 2} ∗n∗(n + m) + 2^d ∗n)$

来一发bitset可以整体除以 64，可以把 n 开得更大

标程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
using namespace std;

const int maxn=90+10,maxmask=1<<20/2+1;
int n,m,d,d1,d2,ans;
bitset<maxn> g0[maxn],g1[maxn],dp[maxmask],f[maxmask];

int main(){
	freopen("y.in","r",stdin);
	freopen("y.out","w",stdout);
	scanf("%d%d%d",&n,&m,&d);
	for(int i=1,u,v,c;i<=m;++i){
		scanf("%d%d%d",&u,&v,&c);
		if(c)
			g1[u][v]=g1[v][u]=true;
		else
			g0[u][v]=g0[v][u]=true;
	}
	d2=d/2;d1=d-d2;
	for(int u=n;u;--u){
		for(int i=0;i<maxmask;++i)
			dp[i].reset();
		dp[1][u]=true;
		for(int x=1;x<1<<d1;++x)
			for(int v=1;v<=n;++v)
				if(dp[x][v]){
					dp[x<<1]|=g0[v];
					dp[x<<1|1]|=g1[v];
				}
		for(int x=0;x<1<<d1;++x)
			f[x][u]=dp[1<<d1|x].any();
	}
	for(int i=0;i<1<<d1;++i)
		for(int j=0;j<1<<d2;++j)
			if((dp[1<<d2|j]&f[i]).any())
				++ans;
	printf("%d\n",ans);
	return 0;
}