算法竞赛进阶指南——搜索

树与图的遍历

可达性统计

#include<iostream>
#include<cstring>
#include<bitset>
using namespace std;
const int N = 3e4 + 10;
int h[N], e[N], ne[N], idx; //链式向前星
int q[N], hh, tt = -1; //队列
int r[N], a[N]; //r是入度，a是拓扑序列
bitset<N> f[N]; //存储当前点可以到哪些点
int n, m;

void add(int x, int y){
    e[idx] = y;
    ne[idx] = h[x];
    h[x] = idx;
    idx++;
}

void topsort(){
    for(int i = 1; i <= n; i++)
        if(!r[i]) q[++tt] = i;
    int k = 0;
    while(hh <= tt){
        int t = q[hh++];
        //存储拓扑序列
        a[k++] = t;
        for(int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            r[j]--;
            if(!r[j]) q[++tt] = j;
        }
    }

}

int main(){
    memset(h, -1, sizeof(h));
    cin>>n>>m;
    int x, y;
    for(int i = 0; i < m; i++){
        cin>>x>>y;
        add(x, y);
        r[y]++;
    }
    topsort();
    //倒序遍历
    for(int i = n - 1; i >= 0; i--){
        int j = a[i];
        f[j][j] = 1;
        for(int k = h[j]; k != -1; k = ne[k])
            f[j] |= f[e[k]]; //累加
    }
    for(int i = 1; i <= n; i++) cout<<f[i].count()<<endl;
    return 0;
}

DFS

小猫爬山

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 20;
int c[N], cnt[N]; //cnt是每辆车的重量
int n, w, ans = 1e9;

//u存储当前第几只猫，k存储当前有几辆车
void dfs(int u, int k){
    if(k >= ans) return;
    if(u > n){
        //这里car肯定小于ans
        ans = k;
        return;
    }
    //放到已有的车中
    for(int i = 1; i <= k; i++){
        if(cnt[i] + c[u] <= w){
            cnt[i] += c[u];
            dfs(u + 1, k);
            cnt[i] -= c[u];
        }
    }
    //放到新的车中
    cnt[k + 1] = c[u];
    dfs(u + 1, k + 1);
    cnt[k + 1] = 0;
}

int main(){
    cin>>n>>w;
    for(int i = 1; i <= n; i++) cin>>c[i];
    //大的先判断
    sort(c + 1, c + 1 + n);
    reverse(c + 1, c + 1 + n);
    dfs(1, 0);
    cout<<ans;
    return 0;
}

数独