双向dfs

为什么要用双向dfs？

如果dfs调栈超过1e5时，那么考虑双向dfs
当进行的变换是可逆的时候，且规定步数的上限时，可以使用双向dfs从源点和终点一起搜索。这样可以把时间从O(n)->O(n/2)

核心就是两个dfs分别处理一半的数据，然后进行调用

附上两个题目

题目一
AtCoder Beginner Contest 184-F
这是一个学长的代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll p[50];
int n,m,cnt;
vector<ll>q1,q2;
void dfs(int x,ll sum){
    if(x==cnt+1){
        q1.push_back(sum);
        return;
    }
    dfs(x+1,sum+p[x]);
    dfs(x+1,sum);
}
void dfs1(int x,ll sum){
    if(x==n+1){
        q2.push_back(sum);
        return;
    }
    dfs1(x+1,sum+p[x]);
    dfs1(x+1,sum);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld",&p[i]);
    }
    cnt=n>>1;
    ll ff=0;
    dfs(1,ff);//处理出前半部分所有的值
    dfs1(cnt+1,ff);//处理出后半部分所有的值
    sort(q2.begin(),q2.end());
    q2.erase(unique(q2.begin(),q2.end()),q2.end());//去重
    ll sum=0;
    for(int i=0;i<q1.size();i++){
        int w=lower_bound(q2.begin(),q2.end(),m-q1[i])-q2.begin();
        if(w==0&&m-q1[i]!=q2[w])continue;
        if(q2[w]!=m-q1[i]){
            w--;
        }
        sum=max(q1[i]+q2[w],sum);
    }
    printf("%lld\n",sum);
    return 0;
}

题目二
送礼物
Acwing 171

附上代码

#include <bits/stdc++.h>

using namespace std;

int const N = 47;
int a[N], cnt = 1, weight[1 << 25], w, n, k, ans;

void dfs1(int u, int sum) {
    if (u == k) {
        weight[cnt++] = sum;
        return;
    }
    
    dfs1(u + 1, sum);  // 不选第u个
    if (sum + 0ll + a[u] <= w) dfs1(u + 1, sum + a[u]);  // 选第u个
}

void dfs2(int u, int sum) {
    
    // 当找完后n/2个后，二分查找小于等于w-s的最大值
    if (u >= n) {
        int l = 0, r = cnt - 1;
        while (l < r) {
            int mid = (l + r + 1) / 2;
            if (sum + 0ll + weight[mid] <= w) l = mid;
            else r = mid - 1;
        }
        ans = max(ans, sum + weight[l]);
        return;
    }
    
    dfs2(u + 1, sum);  // 不选第u个
    if (sum + 0ll + a[u] <= w) dfs2(u + 1, sum + a[u]);  // 选第u个
}

int main() {
    cin >> w >> n;
    int num = 0;
    for (int i = 0, t; i < n; ++i) {
        cin >> t;
        if (t <= w) a[num++] = t;
    }
    n = num;
    k = n / 2;
    
    // 优先大的先搜索
    sort(a, a + n);
    reverse(a, a + n);
    dfs1(0, 0);
    
    // 去重
    sort(weight, weight + cnt);
    cnt = unique(weight, weight + cnt) - weight;
    
    // 第二个dfs
    dfs2(k, 0);
    cout << ans;
    return 0;
}