问题 B: y
时间限制: 1 Sec 内存限制: 256 MB
题面
题面谢绝公开。
题解
考虑双向搜索。
定义$cal_{i,j,k}$表示当前已经搜索状态中是否存在长度为i,终点为j,搜索过边的状态为k的状态。
同样状态设计定义一个$cal2_{i,j,k}$。每个数组搜一半,暴力转移即可。
考虑初始化:$cal_{i,j,k}$数组起点必须是1节点,因此初始值为$cal_{0,1,0}=1$。
而$cal2_{i,j,k}$数组起点任意。因此$cal_{0,i,0}=1(i \in [1,n])$。
考虑最后将两半状态拼成一个状态,枚举断点即最终状态,判定是否有两个状态可以拼接起来当前总状态即可。
至于拼接的方向问题,可以将$cal2$数组的状态定义稍改一下:倒序搜索,当前起点为j,这样无须反转cal2的状态即可拼接。状态转移不变。
(关于为什么要拆开搜索,如果没有拆开,数组定义将是这样:$ cal[21][91][(1<<20)+10]$,大小为2003847846,也就是说不分开的话状态数将爆炸式增长。)
#include<bits/stdc++.h>
#define rint register int
using namespace std;
int n,m,d,ans,len,ren;
bool cal[23][103][20003],cal2[23][103][20003];
vector < pair<int,int> > v[20003];
int main()
{
scanf("%d %d %d",&n,&m,&d);len=d/2,ren=d-len;
cal[0][1][0]=1;for(rint i=1;i<=n;++i)cal2[0][i][0]=1;
for(rint i=1,ST,EN,CL;i<=m;++i)
{
scanf("%d %d %d",&ST,&EN,&CL);
v[ST].push_back(make_pair(EN,CL));
v[EN].push_back(make_pair(ST,CL));
}
for(rint i=0;i<len;++i)
for(rint j=0;j<(1<<i);++j)
for(rint k=1;k<=n;++k)
if(cal[i][k][j])
{
for(rint q=0;q<v[k].size();++q)
cal[i+1][v[k][q].first][(j<<1)+v[k][q].second]=1;
}
for(rint i=0;i<ren;++i)
for(rint j=0;j<(1<<i);++j)
for(rint k=1;k<=n;++k)
if(cal2[i][k][j])
{
for(rint q=0;q<v[k].size();++q)
cal2[i+1][v[k][q].first][(j<<1)+v[k][q].second]=1;
}
for(rint i=0;i<(1<<d);++i)for(rint j=1;j<=n;++j)
if(cal[len][j][i>>ren]&&cal2[ren][j][i&(1<<ren)-1]){ans++;break;}
printf("%d\n",ans);
}
知识兔View Code