[学习笔记]搜索

搜索

有种算法叫暴力剪枝

代码模板

• 添加边

void add(int u,int v)
{
    s[++len].u=u;
    s[len].v=v;
    s[len].next=head[u];
    head[u]=len;
}

• DFS遍历

void dfs(int u)
{
    vis[u]=1;
    for(int i=head[u];i;i=s[i].next)
    {
        int v=s[i].v;
        if(vis[v]) continue;
        dfs(v);
    }
}

• 树的深度

void dfs(int u)
{
    vis[u]=1;
    for(int i=head[u];i;i=s[i].next)
    {
        int v=s[i].v;
        if(vis[v]) continue;
        dep[v]=dep[u]+1;
        dfs(v);
    }
}

• 树的重心

void dfs(int u)
{
    vis[u]=1;
    size[u]=1;
    int max_part=0;
    for(int i=head[u];i;i=s[i].next)
    {
        int v=s[i].v;
        if(vis[v]) continue;
        size[u]+=size[v];
       max_part=max(max_part,size[v]);
    }
    max_part=max(max_part,n-size[u]);
    if(max_part<ans)
    {
        ans=max_part;
        pos=u;  
    }

}

• 图的连通块

void dfs(int u)
{
    vis[u]=1;
    for(int i=head[u];i;i=s[i].next)
    {
        int v=s[i].v;
        if(vis[v]) continue;
        dfs(v);
    }
}
for(int i=1;i<=n;i++)
{
    if(!vis[i])
    {
        cnt++;
        dfs(i);
    }
}

• BFS遍历

void bfs()
{
    memset(dep,0,sizeof(dep));
    queue<int> q;
    q.push(1); d[1]=1;
    while(q.size())
    {
        int u=q.front; q.pop();
        for(int i=head[u];i;i=s[i].next)
        {
            int v=s[i].v;
            dep[v]=dep[u]+1;
            q.push(v);
        }
    }
}

• 拓扑搜索

void topsort()
{
    queue<int>q;
    for(int i=1;i<=n;i++){
        b[i][i]=1;
        if(ru[i]==0) q.push(i);
    }
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=s[i].next)
        {
            int v=s[i].v;
            ru[v]--;
            b[v]|=b[u];
            if(ru[v]==0) q.push(v);
        }
    }
}

EXAM搜索专题训练

A.可达性统计

• 题解

给定一张N个点M条边的有向无环图，分别统计从每个点出发能够到达的点的数量。因为求能到达多少个点具有后效性，所以我们要反向建图。这里用到了一个bitset，bitset能够存储二进制位，然后通过并运算就可以算出他到达了多少个点。因为是无环图，遍历时先从没有子节点的点开始，用ru数组记录有多少子节点，当子节点遍历完了，可以从这个节点继续向父节点遍历。用到了拓扑搜索

#include <bits/stdc++.h>
const int maxn=30010;
using namespace std;
bitset<maxn> b[maxn];
template<class T>
void read(T &res) {
    res = 0;char c = getchar();T f = 1;
    while(c < '0' || c > '9') {
    if(c == '-') f = -1;
    c = getchar();
    }
    while(c >= '0' && c <= '9') {
    res = res * 10 + c - '0';
    c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {putchar('-');x = -x;}
    if(x >= 10) {
    out(x / 10);
    }
    putchar('0' + x % 10);
}
struct node
{
    int u;
    int v;
    int next;
}s[maxn<<2];
int len,head[maxn];
int n,m;
int ru[maxn];
void add(int u,int v)
{
    s[++len].u=u;
    s[len].v=v;
    s[len].next=head[u];
    head[u]=len;
}
void topsort()
{
    queue<int>q;
    for(int i=1;i<=n;i++){
        b[i][i]=1;
        if(ru[i]==0) q.push(i);
    }
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=s[i].next)
        {
            int v=s[i].v;
            ru[v]--;
            b[v]|=b[u];
            if(ru[v]==0) q.push(v);
        }
    }
}
int main()
{
    read(n);
    read(m);
    int x,y;
    for(int i=1;i<=m;i++){
        read(x);
        read(y);
        add(y,x);
        ru[x]++;
    }
    topsort();
    for(int i=1;i<=n;i++){
        out(b[i].count());
        printf("
");
    }
    return 0;
}

bitset用法：https://www.cnblogs.com/RabbitHu/p/bitset.html