搜索算法

搜索

bfs和dfs

bfs搜到的点具有最短路性质，而dfs没有

最短用bfs，奇怪的用dfs

dfs

全排列问题：

dfs的流程：

代码实现：

// 关键时搜索顺序
// dfs是递归
// 回溯时要注意恢复现场
#include <bits/stdc++.h>
using namespace std;
const int N = 10;
int n; // 个数
int path[N];// 路径存储
bool st[N];// 是否被使用
void dfs(int u){
    // 最后一个就直接输出路径
    if(u==n){
        for(int i =0;i<n;i++){
            printf("%d ",pat[i]+1);
        }
        // 每个方案后输出一个换行
        cout<<endl;
        return;
    }
   // 判断当前这个数有没有每用过
    for(int i=0;i<n;i++)
        if(!st[i]){
            // 没有就让当前位置为i
            path[u] = i;
            // 设置其被用过
            st[i] = true;
            // 开始找下一个h位子
            dfs(u+1);
            // 恢复现场
            st[i] = false;
        }
}
int main(){
    cin>>n;
    dfs(0);
    return 0;
}

n皇后问题

代码实现

// 关键时搜索顺序
// dfs是递归
// 回溯时要注意恢复现场
#include <bits/stdc++.h>
using namespace std;
const int N = 20;
int n; // 个数
char g[N][N];
bool row[N],col[N],dg[N],udg[N];// 行和对角线
// 第一种搜索方式
void dfs(int u){
    // 最后一个就直接输出路径
    if(u==n){
       for(int i=0;i<n;i++)puts(g[i]);
        cout<<endl;
        return;
    }
   // 判断当前这个数有没有每用过
    for(int i=0;i<n;i++)
        if(!col[i]&&!dg[u+i]&&!udg[n-u+i]){// 列，对角线，反对角线
            g[u][i]='Q';
            col[i] = dg[u+i]=udg[n-u+i]=true;
            dfs(u+1);
            // 恢复现场
            col[i]=dg[u+i]=udg[n-u+i]=false;
            g[u][i]='.';
        }
}
// 第二种搜索方式 时间较长
void dfs(int x,int y,int s){
	if(y==n)y=0,x++;
    if(x==n){
        if(s==n)
        {
            for(int i=0;i<n;i++)puts(g[i]);
            puts("");
        }
        return;
    }
    // 不放皇后
    dfs(x,y+1,s);
    //放皇后
    if(!row[x]&&!col[y]&&!dg[x+y]&&!ydg[x-y+n]){
        g[x][y] = 'Q';
        row[x]=col[y]=dg[x+y]=udg[x-y+n]=true;
        dfs(x,y+1,s+1);
        row[x] = col[y]=dg[x+y]=udg[x-y+n]=false;
        g[x][y]='.';
    }
}
int main(){
    cin>>n;
    for(int i =0;i<n;i++)
        for(int j=0;j<n;j++)
            g[i][j]='.';
    dfs(0);
    //dfs(0,0,0);
    return 0;
}

树的重心

题目分析：

每个点都枚举一次，记录每次删除后剩余联通分支的最大点数

先说明一下邻接表的存储方式

使用的变量为数组h,e,ne其中，h表示节点，e表示边的终点，ne表示上一条边的终点的索引，举个例子

/*
假设，有边
    1->2,
	2->3,
	3->1,
	1->3,
	1->4

*/
// 我们的插入函数为
int h[6],e[6],ne[6],idx;
void add(int a,int b){
    e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}
/*
按照上面的方式进行插入可得矩阵：
	h	e	ne
0	-1	2	-1
1	 4	3	-1
2	 1	1	-1
3	 2	3	 0
4	-1	4	 3
从上面的矩阵中可以获得邻接表
1->e[h[1]] = e[4]=4->e[ne[4]]=e[3]=3->e[ne[3]]=e[0]=2->e[ne[2]]=-1
2->e[h[2]] = e[1] = 1->e[ne[1]] = -1
3->e[h[3]] = e[2] = 1->e[ne[1]] = -1
简化一下
1->4->3->2->-1
2->1->-1
3->1->-1
*/

AC代码：

#include <bits/stdc++.h>
/*
9
1 2
1 7 
1 4
2 8
2 5
4 3
3 9
4 6
*/
using namespace std;
const int N = 100010,M = N*2;
int n,m;
// 进入点，，出口
int h[N],e[M],ne[M],idx;
// 记录被搜过的点
bool st[N];
int ans = N;

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

//
int dfs(int u){
    st[u] = true;// 标记一下，已经被搜u过了
    // 如果当前点没有被搜过
    int sum = 1,res = 0;
    for(int i = h[u];i!=-1;i=ne[i]){
        int j = e[i];
        if(!st[j]){
            int s = dfs(j);
            res = max(res,s);
            sum+=s;
        }
    }
    res = max(res,n-sum);
    ans = min(ans,res);
    return sum;
}

int main(){
    cin>>n;
    memset(h,-1,sizeof h);
    for(int i = 0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        add(a,b),add(b,a);
    }
    dfs(1);
    cout<<ans<<endl;
    return 0;
}

bfs

走迷宫

边权都是1的时候才用她来求最短路

代码实现

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N = 110;
int n,m;
int g[N][N];//地图
int d[N][N];//到起点的距离
PII q[N*N],Prev[N][N];
int bfs(){
    // 初始化队头队尾
    int hh=0,tt=0;
    q[0]={0,0};
    memset(d,-1,sizeof d);
    d[0][0] = 0;
    // 跑的方向左，下，右，上
    int dx[4] = {-1,0,1,0},dy[4] = {0,1,0,-1};
    // 如果对头比队尾小
    while(hh <= tt){
        // 取出对头
        auto t = q[hh++];
        // 看这四个方向向哪里跑
        for(int i =0;i<4;i++){
            // 决定是走哪个方向
            int x = t.first+dx[i],y=t.second+dy[i];
            // 不越界，方向可走，没走过
            if(x>=0&&x<n&&y>=0&&y<n&&g[x][y]==0&&d[x][y]==-1){
                // 记录当前点距离出发点的距离
                d[x][y] = d[t.first][t.second]+1;
               	// 记录上一个来的点
                Prev[x][y] = t;
                // 队尾加入当前可以走的方向
                q[++tt] = {x,y};
            }
        }
    }
    // 输出路径
    int x=n-1y=m-1;
    while(x||y){
        cout<<x<<' '<<y<<endl;
        auto t = Prev[x][y];
        x = t.first,y=t.second;
    }
    return d[n-1][m-1];;
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin>>g[i][j];
    cout<<bfs()<<endl;
    return 0;
}

图中点的层次

AC代码

/*
4 5
1 2
2 3
3 4
1 3
1 4

结果1
*/
#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
// 到n的最短路，m条边
int n, m;
// h表示起始点，e表示边，ne表示邻接表
int h[N], e[N], ne[N], idx;
int d[N], q[N];
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int bfs()
{
    int hh = 0, tt = 0;
    q[0] = 1;
    memset(d, -1, sizeof d);
    d[1] = 0;
    while (hh <= tt)
    {
        int t = q[hh++];
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (d[j] == -1)
            {
                d[j] = d[t] + 1;
                q[++tt] = j;
            }
        }
    }
    return d[n];
}
int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }
    cout << bfs() << endl;
    return 0;
}

有向图的拓扑序列

有向无环图 == 拓扑图

ac代码

/*
3 3
1 2
2 3
1 3


1 2 3
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m;
int h[N], e[N], ne[N], idx;
int q[N], d[N];
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
bool topsort()
{
    int hh = 0, tt = -1;
    for (int i = 1; i <= n; i++)
    {
        if (!d[i])
            q[++tt] = i;
    }
    while (hh <= tt)
    {
        int t = q[hh++];
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            d[j]--;
            if (d[j] == 0)
                q[++tt] = j;
        }
    }
    return tt == n - 1;
}
int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }
    if (topsort())
    {
        for (int i = 0; i < n; i++)
            printf("%d ", q[i]);
        puts("");
    }
    else
        puts("-1");
    return 0;
}