树与图的遍历

可达性统计

#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肯定小于ansans = 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;
}

数独