搜索与图论

图论

模板

图的存储

/*邻接表存储图*/
//N是点数， M是边数
int h[N], e[M], ne[M], idx, w[M]; //这里w是边的权值

//添加一条边a -> b
void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
//初始化
memset(h, -1, sizeof h);
idx = 0;

理解：这个idx是表示存边信息的数组的下标，所有读入的边都可以对应一个idx，根据出入节点的顺序，可以对应的加到出节点的链上，因为是用数组实现的，而不是链表，所以就用ne数组表示连起来后下一条边的idx，e数组存的是idx这条边的入节点，w是这条边的权重。

遍历节点所连的边

for(int i = h[u]; i != -1; i = ne[i]){
    do...
}

图的DFS遍历

bool st[N];

int dfs(int u){
    st[u] = true;
    
    for(int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        if(!st[j])
                dfs(j);
    }
    
}

图的BFS遍历

//手写队列
int q[N];
bool st[N];

int bfs(){
    //初始化
    int hh = 0, tt = 0;
    q[0] = 1;
    
    while(hh <= tt){
        int t = q[hh++];
        for(int i = h[t]; i != -1; i++){
            int j = e[i];
            if(!st[j]){
                st[j] = true;
                q[++tt] = j;
            }
        }
    }
    
}

DFS

846. 树的重心 - AcWing题库

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 100010;
const int M = 2 * N;

int h[N], e[M], ne[M], idx; 
int st[N];
int n;

int ans = N;

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

int dfs(int u){ //其实就是利用dfs可以求子树长度这一性质，对每个节点遍历求max的子树长度，然后和全局最小ans比较
    
    st[u] = true;
    
    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(n - sum, res); //n-sum表示除了该节点和其字数外的分支
    ans = min(ans, res);
    
    return sum;
}

int main(void){
    memset(h, -1, sizeof h);
    cin >> n;
    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

847. 图中点的层次 - AcWing题库

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 1e5 + 10;

int n, m;

int e[N], ne[N], h[N], idx;
int d[N], q[N];

void add(int a, int b){
    e[idx] = b, ne[idx] = h[a] ,h[a] = idx++; //建立邻接表的时候，用idx只是辅助建表，使用图的时候是不用idx的
}


int bfs(){
    int hh=0, tt =0;
    
    q[0] = 1;
    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(void){
    
    cin >> n >> m;
    memset(d, -1, sizeof d);
    memset(h, -1, sizeof h);
    
    int a, b;
    for(int i = 0; i < m ; i++){
        cin >> a >> b;
        add(a,b);
    }
    
    cout << bfs() << endl;
    
    return 0;
}

848. 有向图的拓扑序列 - AcWing题库

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 1e5 + 10;

int e[N], h[N], ne[N], idx;
int q[N], d[N];
int n, m;

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])
                q[++tt] = j;
        }
    }
    return tt == n-1;
}


int main(void){
    
    cin >> n >> m;
    
    memset(h, -1, sizeof h);
    memset(d, 0, sizeof d);
    
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        add(a, b);
        d[b]++;
    }
    
    if(topsort()){
        for(int i = 0; i < n; i++)  printf("%d ",q[i]); //如果有拓扑序列的话，q[N]就是
    }
    else puts("-1");
    
    return 0;
}

最短路

总体感知理解

Dijkstra
dijkstra算法本质上算是贪心的思想，每次在剩余节点中找到离起点最近的节点放到队列中，并用来更新剩下的节点的距离，再将它标记上表示已经找到到它的最短路径，以后不用更新它了。这样做的原因是到一个节点的最短路径必然会经过比它离起点更近的节点，而如果一个节点的当前距离值比任何剩余节点都小，那么当前的距离值一定是最小的。（剩余节点的距离值只能用当前剩余节点来更新，因为求出了最短路的节点之前已经更新过了）
dijkstra就是这样不断从剩余节点中拿出一个可以确定最短路径的节点最终求得从起点到每个节点的最短距离。

Bellman-Ford
bellman-ford算法进行n-1次更新（一次更新是指用所有边进行一次松弛操作，松弛是指取出一条边，尝试更新这条边起点到终点的距离）来找到到所有节点的单源最短路。bellman-ford算法和dijkstra其实有点相似，该算法能够保证每更新一次都能确定一个节点的最短路，但与dijkstra不同的是，并不知道是那个节点的最短路被确定了，只是知道比上次多确定一个，这样进行n-1次更新后所有节点的最短路都确定了（源点的距离本来就是确定的）。

The longest possible shortest path from source to destination can have “stops”. According to Lemma 24.15 Path-relaxation property in CLRS, after each “relaxation” step, you get and this value remains unchanged ever since. So after times we must finish finding all results for a single-source shortest path problem. You make easily find a counterexample to say why loop for fewer than will fail to find all shortest paths.

现在来说明为什么每次更新都能多找到一个能确定最短路的节点：

1.将所有节点分为两类：已知最短距离的节点和剩余节点。

2.这两类节点满足这样的性质：已知最短距离的节点的最短距离值都比剩余节点的最短路值小。（这一点也和dijkstra一样）

3.有了上面两点说明，易知到剩余节点的路径一定会经过已知节点

4.而从已知节点连到剩余节点的所有边中的最小的那个边，这条边所更新后的剩余节点就一定是确定的最短距离，从而就多找到了一个能确定最短距离的节点，不用知道它到底是哪个节点。

bellman-ford的一个优势是可以用来判断是否存在负环，在不存在负环的情况下，进行了n-1次所有边的更新操作后每个节点的最短距离都确定了，再用所有边去更新一次不会改变结果。而如果存在负环，最后再更新一次会改变结果。原因是之前是假定了起点的最短距离是确定的并且是最短的，而又负环的情况下这个假设不再成立。

Spfa
spfa可以看成是bellman-ford的队列优化版本，正如在前面讲到的，bellman每一轮用所有边来进行松弛操作可以多确定一个点的最短路径，但是用每次都把所有边拿来松弛太浪费了，不难发现，只有那些已经确定了最短路径的点所连出去的边才是有效的，因为新确定的点一定要先通过已知(最短路径的)节点。
所以我们只需要把已知节点连出去的边用来松弛就行了，但是问题是我们并不知道哪些点是已知节点，不过我们可以放宽一下条件，找哪些可能是已知节点的点，也就是之前松弛后更新的点，已知节点必然在这些点中。
所以spfa的做法就是把每次更新了的点放到队列中记录下来，类似于BFS。

朴素Dijkstra

模板

/*Dijkstra模板*/
int dijkstra(){
    memset(dist, 03xf, siszeof dist);//dist[i] <- INF
    dist[1] = 0//dist[1] <- 0,
    
    for i from 1 to n
        t <- -1; //每次都要初始化t
        
        for j from 1 to n //把不在s中的距离最近的点赋值给t
            if(!st[j] && (t == -1 || dist[t] > dist[j]) )
                t <- j;
        
        st[t] = true; //s <- t
        
        for j from 1 to n//用t更新其他点的距离
            if(!st[j])
                dist[j] = min(dist[j], dist[t] + g[t][j]);
    
        
        if(dist[n] == 0x3f3f3f3f) return -1;
        return dist[n];
    
}
//ps:稠密图用邻接矩阵存

习题

849. Dijkstra求最短路 I - AcWing题库

这题是要考虑重边的，注意看一下怎么处理的。

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int  N = 510;

int g[N][N];
int dist[N];
bool st[N];
int n,m;

int dijkstra(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    
    for(int i = 0; i < n; i ++){
        
        int t = -1;    
        for(int j = 1; j <= n; j++)
            if( !st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
    
        st[t] = true;
    
        for(int j = 1; j <= n ; j++)
            if(!st[j])
                dist[j] = min(dist[j], dist[t] + g[t][j]);

    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    
    return dist[n];
}


int main(void){
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b], c); //处理重边
    }
    int t = dijkstra();
    printf("%d ", t);
    
    return 0;
}

堆优化的Dijkstra

用优先队列模拟堆，这样的话堆里元素个数其实可能达到m个，也就是边数，这里应该注意st数组的判断的位置是放在了前面的，因为可能有重边的影响，所以要放在前面continue掉重边。

每次找到最小距离的点沿着边更新其他的点，若dist[j] > distance + w[i]，表示可以更新dist[j]，更新后再把j点和对应的距离放入小根堆中。由于点的个数是n，边的个数是m，在极限情况下（稠密图）。Dijkstra会遍历所有节点的所有边，其实就是遍历所有边，有m次，然后每遍历每条边的时候都要调整堆，堆里面最多有这么多边，因此每一次更新小根堆排序的情况是，一共最多m次更新，因此总的时间复杂度上限是

模板

/*这个模板其实和BFS是有点像的*/
typedef pair<int, int> PII;

int n;      // 点的数量
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边，m,n数据范围是一样的
int dist[N];        // 存储所有点到1号点的距离
bool st[N];     // 存储每个点的最短距离是否已确定

// 求1号点到n号点的最短距离，如果不存在，则返回-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap; //小根堆
    heap.push({0, 1});      // first存储距离，second存储节点编号

    while (heap.size()) //while堆不空
    {
        auto t = heap.top(); //每次取一个
        heap.pop();

        int ver = t.second, distance = t.first;

        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i]) //对该节点遍历
        {
            int j = e[i];
            if (dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

习题

850. Dijkstra求最短路 II - AcWing题库

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>

using namespace std;

const int N = 150010;

typedef pair<int, int> PII; 

int h[N], e[N], ne[N], w[N], idx;
int dist[N];
int n,m;
bool st[N];

void add(int a, int b, int c){
    w[idx] = c;
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++; //这个idx++一定要放到最后
}

int dijkstra()
{
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap; // 定义一个小根堆
    // 这里heap中为什么要存pair呢，首先小根堆是根据距离来排的，所以有一个变量要是距离，其次在从堆中拿出来的时    
    // 候要知道知道这个点是哪个点，不然怎么更新邻接点呢？所以第二个变量要存点。
    heap.push({ 0, 1 }); // 这个顺序不能倒，pair排序时是先根据first，再根据second，这里显然要根据距离排序
    while(heap.size())
    {
        auto t = heap.top(); // 取不在集合S中距离最短的点
        heap.pop();
        int ver = t.second, distance = t.first;

        if(st[ver]) continue;
        st[ver] = true;

        for(int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i]; // i只是个下标，e中在存的是i这个下标对应的点。
            if(dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({ dist[j], j });
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    else return dist[n];
}


int main(void){
    cin >> n >> m;
    memset(h, -1, sizeof(h));
    while(m--){
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }


    int t = dijkstra();
    cout << t << endl;


    return 0;
}

Bellman-Ford

Bellman-Ford可以处理有负权边的图，k次循环的意义是不超过k条边的最短路

看大佬的解释orz：AcWing 853. Bellman_ford算法 - AcWing

模板

int n, m;       // n表示点数，m表示边数
int dist[N];        // dist[x]存储1到x的最短路距离

struct Edge     // 边，a表示出点，b表示入点，w表示边的权重
{
    int a, b, w;
}edges[M];

// 求1到n的最短路距离，如果无法从1走到n，则返回-1。(这里的1换成节点i初始化就是到i的最短路了:leetcode787)
int bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    // 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
    for (int i = 0; i < n; i ++ )
    {
        for (int j = 0; j < m; j ++ )
        {
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            if (dist[b] > dist[a] + w)
                dist[b] = dist[a] + w;
        }
    }

    if (dist[n] > 0x3f3f3f3f / 2) return -1;
    return dist[n];
}

习题

注意：有边数限制的题目要在以上模板的基础上加个备份数组，防止数据被污染。

853. 有边数限制的最短路 - AcWing题库

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int M = 1e4 + 10;
const int N = 510;
int n, m, k;
int back[N], dist[N];

struct{
    int a, b, c;
}e[M];

int bellman_ford(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for(int i = 0; i < k; i++){
        memcpy( back, dist, sizeof dist);
        for(int j = 0; j < m; j++){
            int a = e[j].a, b = e[j].b, w = e[j].c;
            if(dist[b] > w + back[a])
                dist[b] = w + back[a];
        }
    }
    
    return dist[n];
    
}

int main(void){
    cin >> n >> m >> k;
    for(int i = 0 ;i < m; i++)
        scanf("%d%d%d", &e[i].a,&e[i].b,&e[i].c);
    
    int ans = bellman_ford();
    if(ans > 0x3f3f3f3f /2 ) puts("impossible");
    else cout << ans << endl;
    
    
    return 0;
}

Spfa

Spfa优化了Bellman-Ford算法，具体来说就是只考虑可以松弛的边。

看大佬orz：AcWing 851. SPFA算法 - AcWing

模板

int n;
int h[N], e[N], ne[N], idx, w[N];
int st[N], dist[N];
int spfa(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    queue<int> q;
    q.push(1);
    st[1] = true;
    
    while(q.size()){
        int t = q.front;
        q.pop();
        st[t] = false;
        for(int i = h[t], i != -1; i =ne[i]){
            int j = e[i];
            if(dist[j] > dist[t] + w[i]){
                dist[j] = dist[t] + w[i];
                if(!st[j]){
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    }
    return dist[n]; //return到main函数里判断一下

}

习题

851. spfa求最短路 - AcWing题库

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>

using namespace std;

const int N = 1e5 + 10;

int h[N], ne[N], e[N], idx, w[N];
int st[N], dist[N];
int n, m;

int spfa(){
    queue<int> q;
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    q.push(1);
    st[1] = true;
    while(q.size()){
        int t = q.front();
        q.pop();
        st[t] = false;
        for(int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            if(dist[j] > dist[t] + w[i]){
                dist[j] = dist[t] + w[i];
                if(!st[j]){
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    }
    return dist[n];
}


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

int main(void){
    cin >> n >> m;
    memset(h , -1 , sizeof h);
    for(int i = 0; i < m; i++){
        int a, b ,c;
        cin >> a >> b >>c;
        add(a, b ,c);
    }
    
    int t = spfa();
    
    if(t == 0x3f3f3f3f) puts("impossible");
    else cout << dist[n] << endl;
    
    
    
    return 0;
}

AcWing 852. spfa判断负环 - AcWing

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>

using namespace std;

const int N = 1e5 + 10;

int h[N], ne[N], e[N], idx, w[N];
int st[N], dist[N], cnt[N];
int n, m;

int spfa(){
    queue<int> q;
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    for(int i = 1; i <= n; i++){
        st[i] = true;
        q.push(i);
    }
    

    while(q.size()){
        int t = q.front();
        q.pop();
        st[t] = false;
        for(int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            if(dist[j] > dist[t] + w[i]){
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if(cnt[j] >= n) return true;
                if(!st[j]){
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    }
    return false;
}


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

int main(void){
    cin >> n >> m;
    memset(h , -1 , sizeof h);
    for(int i = 0; i < m; i++){
        int a, b ,c;
        cin >> a >> b >>c;
        add(a, b ,c);
    }
    
    int t = spfa();
    
    if(t == false) puts("No");
    else puts("Yes");
    
    
    
    return 0;
}

Floyd

模板

//初始化：
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if (i == j) d[i][j] = 0;
            else d[i][j] = INF;

// 算法结束后，d[a][b]表示a到b的最短距离
void floyd()
{
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

习题

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 210, INF = 1e9;
int n, m, k;
int d[N][N];

void floyd(){

    for(int k = 1; k <= n; k ++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }
    }
    
}

int main(void){
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++){
            if(i == j) d[i][j] = 0;
            else d[i][j] = INF;
        }
    
    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        d[a][b] = min(d[a][b], c);
    }
    
    floyd();
    
    for(int i = 0; i < k; i++){
        int a, b;
        cin >> a >> b;
        if(d[a][b] > INF /2 )    puts("impossible");
        else    cout << d[a][b] << endl;
    }
    
    
    
    
    return 0;
}

最小生成树

朴素Prim

模板

int g[N][N]; //邻接矩阵
int dist[N]; //到集合的距离

int prim(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    for(int i = 0; i < n; i++){
        
        int t = -1;
        for(int j = 1; j <= n; j++)
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        
        if(dist[t] == INF) return INF; //不连通
        
        st[t] = true;
        ans += dist[t]; 
        
        for(int j = 1; j <= n; j++)
                dist[j] = min(dist[j], g[t][j]);
        
    }
    return ans;
}

习题

858. Prim算法求最小生成树 - AcWing题库

Kruskal

并查集知识点

837. 连通块中点的数量 - AcWing题库

模板

int n, m;       // n是点数，m是边数
int p[N];       // 并查集的父节点数组

struct Edge     // 存储边
{
    int a, b, w;

    bool operator< (const Edge &W)const //运算符重载
    {
        return w < W.w;
    }
}edges[M];

int find(int x)     // 并查集核心操作
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int kruskal()
{
    sort(edges, edges + m);

    for (int i = 1; i <= n; i ++ ) p[i] = i;    // 初始化并查集

    int res = 0, cnt = 0;
    for (int i = 0; i < m; i ++ )
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;

        a = find(a), b = find(b);
        if (a != b)     // 如果两个连通块不连通，则将这两个连通块合并
        {
            p[a] = b;
            res += w;
            cnt ++ ;
        }
    }

    if (cnt < n - 1) return INF;
    return res;
}

习题

859. Kruskal算法求最小生成树 - AcWing题库

二分图

二分图染色

模板

int n;      // n表示点数
int h[N], e[M], ne[M], idx;     // 邻接表存储图
int color[N];       // 表示每个点的颜色，-1表示未染色，0表示白色，1表示黑色

// 参数：u表示当前节点，c表示当前点的颜色
bool dfs(int u, int c)
{
    color[u] = c;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (color[j] == -1)
        {
            if (!dfs(j, !c)) return false;
        }
        else if (color[j] == c) return false;
    }

    return true;
}

bool check()
{
    memset(color, -1, sizeof color);
    bool flag = true;
    for (int i = 1; i <= n; i ++ )
        if (color[i] == -1)
            if (!dfs(i, 0))
            {
                flag = false;
                break;
            }
    return flag;
}

习题

AcWing 860. 染色法判定二分图 - AcWing

匈牙利算法

可以结合这个gif理解递归的过程AcWing 861. 二分图的最大匹配 - AcWing

模板

int n1, n2;     // n1表示第一个集合中的点数，n2表示第二个集合中的点数
int h[N], e[M], ne[M], idx;     // 邻接表存储所有边，匈牙利算法中只会用到从第一个集合指向第二个集合的边，所以这里只用存一个方向的边
int match[N];       // 存储第二个集合中的每个点当前匹配的第一个集合中的点是哪个
bool st[N];     // 表示第二个集合中的每个点是否已经被遍历过

bool find(int x)
{
    for (int i = h[x]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true;
            if (match[j] == 0 || find(match[j]))
            {
                match[j] = x;
                return true;
            }
        }
    }

    return false;
}

// 求最大匹配数，依次枚举第一个集合中的每个点能否匹配第二个集合中的点
int res = 0;
for (int i = 1; i <= n1; i ++ ) //这个注意要是从1开始的，不然match[0] = 0会出现bug
{
    memset(st, false, sizeof st);
    if (find(i)) res ++ ;
}
//可能会问说不是两个集合的点么，下标怎么不区分，实际上可以这么理解，就是把刻板印象自环理解为两个标号相同的点连边，两个点分别位于两个集合，这样去理解是不冲突的。

习题

861. 二分图的最大匹配 - AcWing题库

2282. 假期的宿舍 - AcWing题库

最大流

(36条消息) 网络流之最大流算法总结（FF， EK， Dinic）_张宜强的博客-CSDN博客

Ford-Fullkerson

模板

//先挖个坑
//n,m,s,t，分别表示点的个数、有向边的个数、源点序号、汇点序号
INF <- 1e9;

//不断更新余图，增加流量
MAX_FLOW(s, t){
    flow <- 0;
    WHILE(1){
        FOR i <- 0 To n-1
            st[i] <- false; //初始化
        f <- dfs(s, t, INF); 
        IF f == 0 THEN
            return flow;
        flow <- flow + f;
    }
}

//找余图的增广路径，更新余图，并返回该路径的流量
DFS(v, t, f){
    IF v == t THEN //到达汇点
        return f;
    //dfs
    st[v] <- true;
    FOR i <- 0 To n
        e <- edge[v][i]; //s点连的边
        k <- e.vertice; //e的出节点
        IF(!st[k] && e.w > 0) //e.w是这条边的权值
            d <- dfs(k, t, min(f, e.w));
            IF d TEHN //更新正向边和反向边
                e.w <- e.w -d;
                e.inverse_w <- e.inverse_w + d;
                return d;
   return 0;
}

习题

P3376 【模板】网络最大流 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

搜索

搜索漫谈

First question: What is search?

Is it just a way of finding paths on a map?🤔

No🤗, and actually search is about making choices.

搜索大概可以理解为在search space里去寻找符合目标的解，也就是通过决策来去达到目标。

这个search space还真不等同于solution space，但是对于optimal问题的话，应该是the domain of the function to be optimized，也就是solution space 。

搜索其实可以理解为解决问题的一种范式，其实这也是和数学的那种思维不一样的点，数学的思维就是一下子启发性地找到了解决问题的特定思路，而且比较优美。而实际上，很多计算问题是没办法给出特定的公式来指定决策的，并没有说一种对于问题各种变式的统一解法。这其实就应该考虑计算思维，也就是利用算法去实现。首先可以考虑朴素穷举的思维，没有利用问题的特性，也没有考虑启发式设计的那种brute force；然后再去看这个问题有没有其他的设计模式，比如对于optimal问题，有没有优化子结构，能不能用dp和贪心；或者仅仅对于搜索策略，能不能添加启发式方法，以及利用其他方法进行优化。

search can solve lots of different kinds of problems，比较常见的有组合优化问题，约束满足问题。举个例子就很容易理解了，背包问题，最短路问题，后面的小猫爬山习题就是组合优化问题，而八皇后，四色问题这种就属于约束满足问题。

对于组合优化问题，首先来看一下解空间的定义(●’◡’●)， 然后具体的话，先看这个组合优化问题可不可能用dp和贪心整了，要是不行，就考虑搜索，而搜索其实就是 for these points in the solution space, choose a right search sequence that generates the search space which can cover the hole solution space and the elements in it exhaustedly. 但是也不能是爆搜，所以对于搜索，也是要有具体的一些优化方法的。

搜索的优化

搜索大概分为search for a good answer和search for the optimal answer。

对于搜索一个answer的情况大概有以下的讨论：

首先肯定是从爆搜开始优化，在歪果叫做British Museum algorithm，这个算法的消耗就和算法名字一样huge。

然后考虑优化，How can i do better？

先从搜索顺序入手，可以分为从深度入手和从广度入手，然后加上enqueued list也就是对于一个元素只访问一次，相当于st数组的作用，也就是平时用的深搜和宽搜，深搜还有个backtracking的特性。

对于search for a good answer，我们关注的是how far is it to the answer point，可以考虑启发式也就是admissible heuristic，去扩展目前最有可能到达目标的节点。

这里Hill Climbing 的backtracking是防止走到死胡同，找到答案后是不会再去backtracking了。

Hill-climbing类似于depth first，在queue front的那条路径上进行扩展，每次选择最优的，直到死胡同回溯出队or找到good solution.

Hill-climbing searches work by starting off with an initial guess of a solution, then iteratively making local changes to it until either the solution is found or the heuristic gets stuck in a local maximum. There are many ways to try to avoid getting stuck in local maxima, such as running many searches in parallel, or probabilistically choosing the successor state, etc. In many cases, hill-climbing algorithms will rapidly converge on the correct answer. However, none of these approaches are guaranteed to find the optimal solution.

Branch-and-bound solutions work by cutting the search space into pieces, exploring one piece, and then attempting to rule out other parts of the search space based on the information gained during each search. They are guaranteed to find the optimal answer eventually, though doing so might take a long time. For many problems, branch-and-bound based algorithms work quite well, since a small amount of information can rapidly shrink the search space.

In short, hill-climbing isn’t guaranteed to find the right answer, but often runs very quickly and gives good approximations. Branch-and-bound always finds the right answer, but might take a while to do so.

而对于search for the optimal answer，我们关注的是how long have we traveled.可以利用branch and bound分支界限来最优化剪枝(mit这里应该是把branch and bound定义成best-first和剪枝)，另外也可以通过启发式函数进行优化。而算法就可以看为branch&bound + extended list + admissible heuristic。

find a good answer考虑的是enqueued list, 而find an optimal answer考虑的是extended list.

A node is enqueued does not mean that it is extended. In fact, we can enqueue many times the same node, but with different distance value each time, they are just candidates for extension. And we just choose the shortest for extension.

differences between find a good path and find a best path.

搜索习题

爆搜DFS

842. 排列数字 - AcWing题库

//按层数的顺序去搜索
#include<iostream>

using namespace std;

const int N = 10;
int path[N];
bool st[N];
int n;

void dfs(int u){ //u是层数
    
    if(u == n){
        for(int i= 0; i < n; i++)  printf("%d ",path[i]); //按层数打印
        puts("");
        return;
    }
    
    for(int i = 1; i <= n; i++){ //对每个元素枚举
        if(!st[i]){
            path[u] = i;
            st[i] = true;
            dfs(u+1);
            st[i] = false;
        }
    }
}


int main(void){
    cin >> n;
    dfs(0);
    
    return 0;
}

843. n-皇后问题 - AcWing题库

思路一：全排列式搜索顺序，时间复杂度为级。

#include<iostream>

using namespace std;

const int N = 20; //注意那个dg和udg其实是mapping的，数组要开大一点
char g[N][N]; //棋盘
bool col[N], dg[N], udg[N]; //行，列，对角线
int n;

void dfs(int u){ //每一层，也就是每一行
    
    if(u == n){
        for(int i = 0; i < n; i++) puts(g[i]);
        puts("");
        return;
    }
            
    
    for(int i = 0; i < n; i++){
        if(!col[i] && !dg[i+u] && !udg[n-i+u]){
            g[u][i] = 'Q';
            col[i] = dg[i+u] = udg[n-i+u] = true;
            dfs(u+1);
            g[u][i] = '.';
            col[i] = dg[i+u] = udg[n-i+u] = false;
        }
    }
    
}

int main(void){
    cin >> n;
    
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            g[i][j] = '.'; //进行初始化
    
    dfs(0);
    
    
    return 0;
}

思路二：对每个位置进行枚举，时间复杂度为级别

#include<iostream>

using namespace std;

const int N = 20; //注意那个dg和udg其实是mapping的，数组要开大一点
char g[N][N]; //棋盘
bool row[N], col[N], dg[N], udg[N]; //行，列，对角线
int n;

void dfs(int x, int y, int s){ // x,y是表示格子，s是皇后的个数
    if(y == n){ //处理出界情况
        x += 1;
        y = 0;
    }
    
    if(x == n){ //搜索完了而且皇后也放完了
        if(s == n){
            for(int i = 0; i < n; i++)
                    puts(g[i]);
                puts("");
        }
        return;
    }

    if(!row[x] && !col[y] && !dg[x+y] && !udg[x-y+n]){
        g[x][y] = 'Q';
        col[y] = dg[x+y] = udg[n-y+x] = row[x] = true;
        dfs(x,y+1,s+1);
        g[x][y] = '.';
        col[y] = dg[x+y] = udg[n-y+x] = row[x] = false;
    }
    
    // 不放皇后
    dfs(x, y+1, s);
    
}

int main(void){
    cin >> n;
    
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            g[i][j] = '.'; //进行初始化
    
    dfs(0,0,0);
    
    
    return 0;
}

165. 小猫爬山 - AcWing题库

小猫爬山其实是和八皇后的思路2有点像，也是对每个状态进行枚举

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 20;

int cat[N], sum[N]; 
int ans = N;
int n, m; //小猫总数和重量限制

void dfs(int u, int k){ //k辆车，0~k-1
    if(k >= ans) return;
    
    if(u == n){
        ans = k;
        return;
    }
    
    //放到以前的车子里
    for(int i = 0; i < k; i++){
        if(sum[i] + cat[u] <= m){
            sum[i] += cat[u];
            dfs(u+1, k);
            sum[i] -= cat[u];
        }
    }    
    
    //开新车
    sum[k] = cat[u];
    dfs(u+1, k+1);
    sum[k] = 0;
    
}


int main(void){
    cin >> n >> m;
    for(int i = 0 ; i < n; i++) scanf("%d", &cat[i]);
    sort(cat, cat+n);
    reverse(cat, cat+n);
    
    dfs(0, 0);
    cout << ans << endl;
    
    return 0;
}

迷宫型 BFS

844. 走迷宫 - AcWing题库

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 105;
typedef pair<int, int> PII;

PII q[N * N], path[N][N];

int n, m;
int g[N][N], d[N][N];

int bfs(){
    int hh = 0, tt = 0; //队头和队尾
    q[0] = {0,0};   //队列里面存的是pair，也就是点的坐标
    
    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 && y >= 0 && x < n && y < m && g[x][y] == 0 && d[x][y] == -1){
                //path[x][y]= t; //输出路径
                d[x][y] = d[t.first][t.second] + 1;
                q[++tt] = {x,y};
            }
        }
    }
    return d[n -1][m -1];
}


int main(void){

    cin >> n >> m;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            cin >> g[i][j];
    

    cout << bfs() << endl;
    
    //输出路径        
    // int x = n-1, y = m-1;
    // while(x || y){
    //     cout << x << ',' << y << endl;
    //     int tempx = path[x][y].first, tempy = path[x][y].second;
    //     x = tempx, y =tempy;
    // }
    
    return 0;
}

AcWing 845. 八数码 - AcWing

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<unordered_map>

using namespace std;

int bfs(string start){
    string end = "12345678x";
    
    //map一下，把状态对应到节点，每个节点对应一个距离
    unordered_map<string, int> d;
    d[start] = 0;
    
    queue<string> q;
    q.push(start);
    
    while(q.size()){
        auto t = q.front();
        q.pop();
        
        int distance = d[t];
        if(t == end) return d[t];
        
        //状态转移,把1维数组2维化
        int k = t.find('x');
        int x = k/3, y = k % 3;
        
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
        
        for(int i = 0; i < 4; i++){
            int a = x + dx[i], b = y + dy[i];
            if(a >= 0 && a < 3 && b >= 0 && b < 3){
                int temp = a * 3 + b;
                swap(t[k], t[temp]);    
                if(!d.count(t)){
                    q.push(t);
                    d[t] = distance + 1;
                }
                swap(t[k], t[temp]);
            }
            
        }
    }
    return -1;
}


int main(void){
    
    char c;
    string start;
    for(int i = 0; i < 9; i++){
        cin >> c;
        start += c;
    }
        
    cout << bfs(start) << endl;
    
    return 0;
}