[2018.10 雅礼] y 题解【双向搜索】【状态压缩】【递推】
点击量:198
可以用双向搜索来减少枚举的一道题。叫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;
}
… [Trackback]
[…] Here you can find 47164 additional Info on that Topic: wjyyy.top/1913.html […]
… [Trackback]
[…] Find More here to that Topic: wjyyy.top/1913.html […]