[2018.10 雅礼] y 题解【双向搜索】【状态压缩】【递推】

作者: wjyyy 分类: 二进制,双向搜索,图论,枚举,状态压缩,解题报告,递推 发布时间: 2018-10-15 21:46

点击量:20

 

    可以用双向搜索来减少枚举的一道题。叫meet-in-middle应该更合理。

 

题目背景

\(\frac 14\)遇到了一道水题,叕完全不会做,于是去请教小\(\text{D}\)。小\(\text{D}\)懒得理\(\frac 14\),直接就离开了。于是,\(\frac 14\)只好来问你,这道题是这样的:

 

题目描述

给定一个无向图,\(n\)个点(从\(1\)开始编号)、\(m\)条边(长度为\(1\)),每条边有一个权值\(c(c\in \{0,1\})\)。

 

一条路径,可以表示为一个长度为经过边数的\(01\)串,串的第\(i\)位为经过的第\(i\)条边的权值。

 

两条路径相同,当且仅当表示其的\(01\)串相同。

 

求从\(1\)号点出发、长度为\(d\)的路径种数。

 

输入输出格式

输入格式:

从文件y.in中读入数据。

 

第一行,三个整数,\(n,m,d\)。

 

接下来\(m\)行,每行三个整数\(u,v,c\),代表一条边连接\(u\)和\(v\),权值为\(c\)。

 

输出格式:

输出到文件y.out中。

 

输出一行,一个整数,代表答案。

输入输出样例

输入样例#1:

3 2 3
1 2 0
1 3 1
输出样例#1:

4

说明

样例解释

\(1\rightarrow 2\rightarrow 1\rightarrow 2\Rightarrow 000\)

\(1\rightarrow 2\rightarrow 1\rightarrow 3\Rightarrow 001\)

\(1\rightarrow 3\rightarrow 1\rightarrow 2\Rightarrow 110\)

\(1\rightarrow 3\rightarrow 1\rightarrow 3\Rightarrow 111\)

数据范围

\(\text{Subtask}\) 分值 \(n \le\) \(d \le\) 其他限制
\(1\) \(21\) \(30\) \(4\)
\(2\) \(39\) \(70\) \(13\)
\(3\) \(12\) \(90\) \(20\) 保证\(c\in \{0\}\)
\(4\) \(9\) \(30\) \(20\)
\(5\) \(19\) \(90\) \(20\)

 

题解:

    这个题的题意比较好懂。我们如果跟着题意从1号节点开始搜索/递推,到后面的状态就会越来越多。我们考虑状压,就知道到哪个点,哪个状态有没有走过。注意这个题的边是可重的,而且互不影响。

 

    定义\(g_{(i,sta)}\)表示从\(1\)走到\(i\)存在一条种类为\(sta_{(2)}\)的路径。让每个点每次枚举转移来源和转移状态,转移\(d\)次统计答案。时间复杂度是\(O(n^2\cdot 2^d)\),后三组数据都无法过掉,可以看出我考场上怎么就没看出\(2^d\)对复杂度作了主要贡献,此时我们考虑什么?折半/双向搜索/meet-in-middle,因为答案的前后半段贡献可以累加。

 

    此时我们把路径分成从\(1\)出发的前半段,和到达任意节点结束的后半段,分别用\(g_{(i,d,sta)},f_{(i,d,sta)}\)来表示当前节点、路径长度、状态,其中第二维可以被滚掉,但是没有必要。然后像之前一样转移即可,只是初始化会发生变化,\(\forall i\in[1,n]\ f[i][0][0]=1\),\(g[1][0][0]=1\)。最后再枚举连接节点把它们拼凑起来就可以了,一种路线只算一次,不要算多了:)。

 

    写了两份代码,一种是按照上面写的,另一种压了空间,算是一种技巧吧,就是把\(d\)那一维压在\(sta\)里,作为\(sta\)的最高位,确定了这一状态的\(d\)。这一思想对一些时间常数和空间要求大的题比较有用。

Code:

#include<cstdio>
#include<cstring>
bool O[100][100],I[100][100];
bool f[100][12][1<<10],g[100][12][1<<10];
int main()
{
    int n,m,d,u,v,w;
    scanf("%d%d%d",&n,&m,&d);
    for(int i=1;i<=n;++i)
        f[i][0][0]=1;//f表示任意路径到i结束
    g[1][0][0]=1;//g表示从1开始 到i结束
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&u,&v,&w);
        if(w)
        {
            I[u][v]=1;
            I[v][u]=1;
        }
        else
        {
            O[u][v]=1;
            O[v][u]=1;
        }
    }
    for(int i=1;i<=(d+1)/2;++i)
        for(int j=1;j<=n;++j)
            for(int k=1;k<=n;++k)
                for(int p=0;p<(1<<(i-1));++p)
                {
                    if(O[j][k])
                    {
                        f[j][i][p]|=f[k][i-1][p];
                        g[j][i][p]|=g[k][i-1][p];
                    }
                    if(I[j][k])
                    {
                        f[j][i][p|(1<<(i-1))]|=f[k][i-1][p];
                        g[j][i][p|(1<<(i-1))]|=g[k][i-1][p];
                    }
                }
    int sum=0;
    int upi=1<<((d+1)>>1);
    int upj=1<<(d>>1);
    for(int i=0;i<upi;++i)
        for(int j=0;j<upj;++j)
        {
            int flag=0;
            for(int k=1;k<=n;++k)
                if(f[k][(d+1)>>1][i]&&g[k][d>>1][j])
                    flag=1;
            sum+=flag;
        }
    printf("%d\n",sum);
    return 0;
}

 

Code++:

#include<cstdio>
#include<cstring>
bool O[100][100],I[100][100];
bool f[100][1<<11],g[100][1<<11];
int main()
{
    int n,m,d,u,v,w;
    scanf("%d%d%d",&n,&m,&d);
    for(int i=1;i<=n;++i)
        f[i][1]=1;//f表示任意路径到i结束
    g[1][1]=1;//g表示从1开始 到i结束
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&u,&v,&w);
        if(w)
        {
            I[u][v]=1;
            I[v][u]=1;
        }
        else
        {
            O[u][v]=1;
            O[v][u]=1;
        }
    }
    for(int i=1;i<=(d+1)/2;++i)
        for(int j=1;j<=n;++j)
            for(int k=1;k<=n;++k)
                for(int p=0;p<(1<<(i-1));++p)
                {
                    if(O[j][k])
                    {
                        f[j][p|(1<<i)]|=f[k][p|(1<<(i-1))];
                        g[j][p|(1<<i)]|=g[k][p|(1<<(i-1))];
                    }
                    if(I[j][k])
                    {
                        f[j][p|(1<<(i-1))|(1<<i)]|=f[k][p|(1<<(i-1))];
                        g[j][p|(1<<(i-1))|(1<<i)]|=g[k][p|(1<<(i-1))];
                    }
                }

    int sum=0;
    int upi=1<<((d+1)>>1);
    int upj=1<<(d>>1);
    for(int i=0;i<upi;++i)
        for(int j=0;j<upj;++j)
        {
            int flag=0;
            for(int k=1;k<=n;++k)
                if(f[k][i|upi]&&g[k][j|upj])
                    flag=1;
            sum+=flag;
        }
    printf("%d\n",sum);
    return 0;
}

说点什么

avatar
  Subscribe  
提醒
/* */