「题解」:y

问题 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
计算机