题目链接:
咕
闲扯:
这题暴力分似乎挺多, 但是一些奇奇怪怪的细节没注意 RE 了, 还是太菜了
分析:
首先我们考虑最 naiive 的状压 DP ,\(f[u][v][state]\) 表示 u 开头, v 结尾是否存在一条表示为 state 的路径, 这个好转移不讲了, 但是由于 d 的范围时间复杂度过大, 于是考虑折半搜索
我们把一条最终路径的路径分成两部分 \(p=(d+1)/2\)(其实就是上取整),\(q=d-p\), 显然 \(p>=q?\)
于是我们可以把一条路径长度看成两部分, 一条从 1 开始, 长度为 p 的路径, 另一条以某点为开头, 长度为 q, 终点恰好与第一条路径接上.
然后这时候我们就用 \(ff[state][x]\) 表示是否存在一条以 x 为开头, 表示为 state 的路径, 这个 DP 数组怎么得到呢?
我们枚举起点 \(st\), 再用一个数组 \(f[state][x]\) 表示是否存在一条 st 开头, x 结尾, 状态为 state 的路径, 这个非常好转移我们从小到达枚举状态再根据两点之间是否连边转移
于是如果 \(f[state]\) 中存在一个值为 1 的元素, 那么 \(ff[state][st]=1\)
由于是折半路径, 我们只需要将路径状态压为一个 p 位二进制数就好了
注意最后路径是从 1 开始, 我们方便起见倒着枚举起点, 最后枚举长度为 p 的前一半状态, 和长度为 q 的后一半状态, 如果存在一点 v,\(ff[state_1][v]\)&\(f[state_2][v]==1\), 那么方案数加 1
同时预防前导 0 还需要特殊处理
还发现 DP 数组都是 0/1 序列, 使用 bitset 减少操作时间复杂度
代码:
- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- #include <algorithm>
- #include <cctype>
- #include <iostream>
- #include <bitset>
- #define ll long long
- #define ri register int
- using std::min;
- using std::bitset;
- using std::max;
- template <class T>inline void read(T &x){
- x=0;int ne=0;char c;
- while(!isdigit(c=getchar()))ne=c=='-';
- x=c-48;
- while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
- x=ne?-x:x;return ;
- }
- const int maxn=95;
- const int inf=0x7fffffff;
- const int N=1<<20-1;
- bitset <maxn> g0[maxn],g1[maxn],f[N],ff[N];
- int p,q;
- inline void clear(){
- for(ri i=0;i<N;i++)f[i].reset();
- return ;
- }
- ll ans=0;
- int n,m,d;
- int main(){
- int x,y,z;
- #ifdef Luogu
- freopen("y2.in","r",stdin);
- freopen("y2.out","w",stdout);
- #endif
- read(n),read(m),read(d);
- int p=(d+1)/2,q=d-p;
- int o=1<<p,oo=1<<q;
- for(ri i=1;i<=m;i++){
- read(x),read(y),read(z);
- if(z==1)g1[x][y]=g1[y][x]=1;
- else g0[x][y]=g0[y][x]=1;
- }
- for(ri now=n;now>=1;now--){
- clear();
- f[1][now]=1;// 避免前导 0
- for(ri i=1;i<o;i++){
- for(ri j=1;j<=n;j++){
- if(f[i][j]){//now 循环中, f[state][v] 表示 now 开头, v 结尾状态为 state 的路径是否存在
- f[i<<1]|=g0[j],f[i<<1|1]|=g1[j];
- }
- }
- }//ff[state][u] 表示从 u 开头, 是否能走出一条状态为 state 的路径
- for(ri i=0;i<o;i++)ff[i][now]=f[o|i].any();
- }
- for(ri i=0;i<o;i++){
- for(ri j=0;j<oo;j++){
- if((ff[i]&f[oo|j]).any())ans++;
- }
- // 若存在点 x f[state_1][x]=1 并且 ff[state_2][x]=1
- // 说明从 x 开头能走出一条 state_2 的路径
- // 从 1 开头, x 结尾, 又能走出一条 state_1 的路径, 这样就能连起来成为一条合法的路径
- }
- printf("%lld\n",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2794698.html