算法竞赛进阶指南 小猫爬山 可达性统计

题目链接：https://www.acwing.com/problem/content/167/
小猫爬山，基础dfs，将当前猫和车传入参量很好做

#include<bits/stdc++.h>
using namespace std;
int n,w;
int cab[22],d[22];
int ans;
void dfs(int now,int cnt)
{
// cout<<ans<<endl;
    if(cnt>=ans)return;
    if(now==n+1)
    {
        ans=cnt;
        return;
    }
    for(int i=1;i<=cnt;i++)
    {
        if(cab[i]+d[now]<=w)
        {
            cab[i]+=d[now];
            dfs(now+1,cnt);
            cab[i]-=d[now];
        }
    }
    cab[cnt+1]=d[now];
    dfs(now+1,cnt+1);
    cab[cnt+1]=0;
}
bool cmp(int a,int b)
{
    return a>b;
}

int main()
{
    cin>>n>>w;
    for(int i=1;i<=n;i++)
        cin>>d[i];
    sort(d+1,d+n+1,cmp);
    ans=20;
    dfs(1,0);
    cout<<ans<<endl;
   return 0;
}

题目链接：https://www.acwing.com/problem/content/166/
最重要的是状态压缩，bitset压位+拓扑排序

#include<bits/stdc++.h>
using namespace std;
const int maxn = 30050;
int n,m;
bitset<maxn>f[maxn];
int Next[maxn],ver[maxn],head[maxn];
int tot;
void add(int x,int y)
{
    ver[++tot] = y;
    Next[tot] = head[x];
    head[x]=tot;
}
int a[maxn];int cnt;
int deg[maxn];
void topsort()
{
    queue<int>q;
    for(int i=1;i<=n;i++)
    {
        if(!deg[i])
            q.push(i);
    }
    while(q.size())
    {
        int x = q.front();
        q.pop();
        a[++cnt]=x;
        for(int i=head[x];i;i=Next[i])
        {
            int y = ver[i];
            if(--deg[y]==0)
            q.push(y);
        }
    }
}

int main()
{
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int x,y;
        cin>>x>>y;
        add(x,y);
        deg[y]++;
    }
    topsort();
    for(int i=cnt;i>0;i--)
    {
        int y = a[i];
        f[y][y]=1;
        for(int j=head[y];j;j=Next[j])
        {
            f[y]|=f[ver[j]];
        }
    }
    for(int i=1;i<=n;i++)
    {
        cout<<f[i].count()<<endl;
    }

}