提高组刷题营 DAY 1 下午

DFS

深度优先搜索

通过搜索得到一棵树形图

策略：只要能发现没走过的点，就走到它。有多个点可走就随便挑一个，如果无路可走就回退，再看有没有没走过的点可走。

在图上寻找路径【少数可用最短路解决】：最短路不能解决路径有顺序的，也就是如果路径的边权与之前经过的点火这路有关，那就只能深搜

解决递归形式的问题

有后效性的选择问题

组合问题

状态可能很多，因此数据范围一般较小

1、状态表示

2、剪枝

剪枝的方法：

最优答案剪枝

记忆化剪枝

可行性剪枝

……

1、洪水[ 1s 32M ]

题解

数据范围小，搜索

2、辛苦的老园丁 [1s 128M] [1s 32M]

题解

建反图找团（简单地说，团是G的一个完全子图）

原来输入建图是标记的两点之间不能有连边，建反图之后，连边的就是可以连通的

剪枝：

1.如果一个点与点i当前没有连边，那么之后永远都不会连边，那么就可以把点i从最大团候选中删掉

2.利用可行点剪枝 sum+tot<=ans ，舍弃

3.利用当前答案剪枝ans(2)+tot<=ans

（tot 是团不断累加的权值，sum是序列里面剩下的所有东西的权值和

若sum+tot<=ans ，舍弃）

可能组成最大团的点一开始在一个序列里

取出一个点，不断扩展，当序列为空，扩展完了

首先拿出1 ，那么序列被更新为与1相连的点

不断扩展，直到队列为空，找完团了

--->sum+tot<=ans

最大团主函数：

为什么找最大团而不是最大独立集呢？？

3、生日蛋糕 [ 1s 10M]

题解

4、靶形数独[2s128M]

题解

5、棋盘分割 [1s 16M]

题解

BFS

宽度优先搜索

1、密室逃脱 [ 1s 64M ]

题解

queue<pair<int,int> > Q;
int FindPath(pair<int,int> b,pair<int,int> e) {
    for (int i=0;i<n;++i) for (int j=0;j<m;++j) dis[i][j]=1e9+10;
    Q.push(b); dis[b.first][b.second]=0;
    while (!Q.empty()) {
        pair<int,int> u=Q.front(); Q.pop();
        int x=u.first,y=u.second;
        for (int i=0;i<4;++i) {
            int tx=x+dx[i],ty=y+dy[i];
            if (CoordValid(tx,ty) && mp[tx][ty]!=0 && dis[tx][ty]>dis[x][y]+1) {
                dis[tx][ty]=dis[x][y]+1;
                Q.push(make_pair(tx,ty));    
            }
        }
    }
    return dis[e.first][e.second];
}