搜索与图论板子库

这里的python全是python3的
详情请见acwing，acwing赛高
力求快、准、狠、短

---

搜索与图论

#DFS

##排列与组合之类的

----c++版

全排列
https://www.acwing.com/problem/content/844/

#include<iostream>
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 ",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;//不需要拔开path的，因为每次都会覆盖掉
        }
}
int main(){
    cin>>n;
    dfs(0);
    return 0;
}

全组合
https://www.acwing.com/problem/content/description/95/
递归写法

#include<iostream>
using namespace std;
const int N=30;
int n,m;
bool st[N];
int path[N];

void comb(int u){
    if(u==m){
        for(int i=0;i<m;i++)printf("%d ",path[i]);
        puts("");
        return;
    }
    for(int i=1;i<=n;i++){
        if(u&&i<path[u-1])continue;//古典概型的列组合方法，后面一定比前面大
        if(!st[i]){
            st[i]=true;
            path[u]=i;
            comb(u+1);
            st[i]=false;
        }
    }
}

int main(){
    cin>>n>>m;
    comb(0);
    return 0;
}

##n皇后

----c++版

https://www.acwing.com/problem/content/845/

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N=20;
int n;
char g[N][N];
bool col[N],dg[N],udg[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[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]='.';
        }
    }
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            g[i][j]='.';
    dfs(0);return 0;
}

#BFS

##走迷宫

----c++版

https://www.acwing.com/problem/content/description/846/

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=110;
typedef pair<int, int> PLL;

int n,m;
int g[N][N];
int d[N][N];
PLL q[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<m&&g[x][y]==0&&d[x][y]==-1){
                d[x][y]=d[t.first][t.second]+1;
                q[++tt]={x,y};
            }
        }
    }
    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();
    
    return 0;
}

##八数码

----c++版

https://www.acwing.com/problem/content/847/

//状态表示
//状态转移
//路径存储
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<queue>
#include<cstring>
using namespace std;

int bfs(string start){
    string end = "12345678x";//终点
    
    queue<string>q;
    unordered_map<string, int>d;//距离数组
    
    q.push(start);
    d[start]=0;//unordered_map的用法
    
    int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};//对称写法
    
    while(q.size()){
        auto t=q.front();
        q.pop();
        int distance=d[t];//distance为当前节点的步数
        if(t==end)return distance;
        //状态转移
        int k=t.find('x');
        int x=k/3,y=k%3;//小技巧，一维数组下标转换为二维数组下标
        
        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){
                swap(t[k], t[a*3+b]);//状态转移，获得新状态
                //走过的一定是最短的
                if(!d.count(t)){//如果没走过
                    d[t]=distance+1;//加上距离
                    q.push(t);//加入待拓展队列
                }
                swap(t[k], t[a*3+b]);
            }
        }
    }
    return -1;
}

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

#树与图的深度优先遍历

树是无环连接图，图分为有向图和无向图，无向图是特殊的有向图
有向图的存储可以用邻接矩阵（存稠密图，有重边的只留一条）和邻接表
图的遍历可以通过bfs和dfs

##树的重心

----c++版

https://www.acwing.com/problem/content/848/

#include<iostream>
#include<algorithm>
#include<cstring> # 使用memset
using namespace std;

const int N=1e5+10,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;//标记一下已经搜过
    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;
}

#树与图的广度优先遍历

##图中点的层次

----c++版

https://www.acwing.com/problem/content/849/

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N=1e5+10;
int n,m;
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);//-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(){
    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;
}

#拓扑排序

##有向图的拓扑序列

图的宽搜应用，针对有向图
在图中存在一种序列，使得按序列所有的有向边都指向一个方向

有向无环图（拓扑图）一定存在一个拓扑序列，一定有一个入度为0的点。
反证法：如果一个有n个有限点的有向无环图没有入度为0的点，每个点必然可以由入度不为0的地方找到上一个点，当找的点数大于n，由抽屉原理，必然存在一个环路，矛盾

入度：有几条边指向；出度：有几条边出去
所有入度为零的点都能排在最前边的位置

----c++版

https://www.acwing.com/problem/content/850/

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int n,m;
int h[N],e[N],ne[N],idx;
int q[N],d[N];//d存每个点的入度

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;//从0开始的
}

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);
        d[b]++;
    }
    if(topsort()){
        for(int i=0;i<n;i++)printf("%d ",q[i]);
    }else puts("-1 ");
    return 0;
}

#dijkstra

##一

----c++版

https://www.acwing.com/problem/content/851/

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=510;
int n,m;
int g[N][N];
int dist[N];//从1走到n号点的当前最短距离
bool st[N];//确定了最短路的点的集合

int dijkstra(){
    memset(dist, 0x3f, sizeof dist);
    dist[1]=0;
    for(int i=0;i<n;i++){//迭代n次
        int t=-1;//每次找出没确定最短路的点之中到 确定最短路的点的集合 的距离最小的点
        for(int j=1;j<=n;j++)
            if(!st[j]&&(t==-1||dist[t]>dist[j]))
                t=j;
        st[t]=true;//将找到的点加入确定最短路的点的集合
        if(t==n)break;
        for(int j=1;j<=n;j++)//实际上有m次
            dist[j]=min(dist[j],dist[t]+g[t][j]);//用新的点的最短路去尝试更新所有当前最短路（也包括曾确定的）
    }
    if(dist[n]==0x3f3f3f3f)return -1;
    return dist[n];
}

int main(){
    scanf("%d%d",&n,&m);
    memset(g, 0x3f, sizeof g);
    while(m--){
        //由于有重边和自环
        int a,b,c;scanf("%d%d%d",&a,&b,&c);
        g[a][b]=min(g[a][b], c);//不用管自环，用不到
    }
    int t=dijkstra();
    printf("%d",t);
    return 0;
}

##二 堆优化版

在朴素版中有【找出没确定最短路的点之中到 确定最短路的点的集合 的距离最小的点】这个操作，
朴素版用循环实现，堆优化直接用优先队列实现，省去了循环的过程

----c++版

你可以手写堆，这样堆里可以维持n个数，也可以使用c++提供的优先队列，但队列里可能有m个数
个人觉得堆优化版的dijkstra更好理解，更直接
https://www.acwing.com/problem/content/852/

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
//稀疏图用邻接表存
const int N=1e6+10;
int n,m;
int h[N],e[N],w[N],ne[N],idx;
int dist[N];
bool st[N];
typedef pair<int, int>pll;//由于我们还需要知道节点编号

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

int dijkstra(){
    memset(dist, 0x3f, sizeof dist);
    dist[1]=0;
    priority_queue<pll, vector<pll>, greater<pll>>heap;//小根堆
    heap.push({0,1});//1到1最短距离是0
    while(heap.size()){
        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});//把更新过的最短路加到堆里，虽然更短路会被堆pop掉，但没关系，因为distj是确实更新了，且堆只是为了找还在集合外的点
            }
        }
    }
    if(dist[n]==0x3f3f3f3f)return -1;
    return dist[n];
}

int main(){
    scanf("%d%d",&n,&m);
    memset(h, -1, sizeof h);
    while(m--){
        //用邻接表存，有重边也没事了，算法保证一定会选最短边
        int a,b,c;scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    int t=dijkstra();
    printf("%d",t);
    return 0;
}

#bellman-ford

bellman-ford 的存边方式比较简单，只要能遍历到所有边就行，可以用最简单的开个结构体的方式
基本是两重循环

for 遍历n次：
    for 从a到b权值w的所有边：
        dist[b]=min(dist[b], dist[a]+w);

每次判断1到b的距离能不能用这条边来更新
遍历完保证对所有边满足dist[b]<=dist[a]+w， 这是松弛操作
bellman-ford可以处理负权边
如果有负权回路，最短路不一定存在

外层循环迭代k次，dist数组的含义是：不超过k条边到各点的最短路距离
如果第n次迭代还有边被更新，说明存在一条最短路上面有n条边，由于最多才n个点，抽屉原理，所有必然有两个点编号一样，存在负环。

有可能有负环又存在最短路的，
如果用spfa，则一定要求图中没有负环

##有边数限制的最短路

这个只能用bellman-ford，一般spfa比bellman-ford好

----c++版

https://www.acwing.com/problem/content/855/

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=510,M=10010;
int n,m,k;
int dist[N],backup[N];
struct edge{
    int a,b,w;
}edges[M];

int bellmanford(){
    memset(dist, 0x3f, sizeof dist);
    dist[1]=0;
    for(int i=0;i<k;i++){
        //备份dist数组，因为可能出现串联
        //即在此次更新过程中用此次更新的距离去更新其他距离，这样限制不了步数
        //需要在每次更新时都使用上一次迭代的结果
        memcpy(backup, dist, sizeof dist);
        for(int j=0;j<m;j++){
            int a=edges[j].a,b=edges[j].b,w=edges[j].w;
            dist[b]=min(dist[b],backup[a]+w);
        }
    }
    //大于一个比较大的数，因为到不了的点之间的负权边可能会把无穷大更新了
    if(dist[n]>0x3f3f3f3f/2)return -1;
    return dist[n];
}

int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i<m;i++){
        int a,b,w;scanf("%d%d%d",&a,&b,&w);
        edges[i]={a,b,w};
    }
    int t=bellmanford();
    if(t==-1)puts("impossible");
    else printf("%d", t);
    return 0;
}

#spfa

网格型图易卡spfa

##spfa求最短路

对bellman-ford的优化
针对松弛操作的优化，如果dist[b]变小了，一定是因为dist[a]变小了，
如果有变小的距离，针对这个距离把之后的全部更新就得
更新过谁，再拿谁来更新别人

----c++版

实现和dijkstra很像
https://www.acwing.com/problem/content/853/

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int ,int> pll;
const int N=100010;
int n,m;
int h[N],w[N],e[N],ne[N],idx;
int dist[N];
bool st[N];

void add(int a,int b,int c){
    e[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx++;
}
//类似宽搜的方式
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]){//如果已经在就不用再加了
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }
    if(dist[n]==0x3f3f3f3f)return -1;
    return dist[n];
}

int main(){
    scanf("%d%d",&n,&m);
    memset(h, -1, sizeof h);
    while(m--){
        int a,b,c;scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    int t=spfa();
    if(t==-1)puts("impossible");
    else printf("%d",t);
    return 0;
}

##spfa判断负环

----c++版

https://www.acwing.com/problem/content/854/

// 思路和bellmanford差不多，抽屉原理，时间复杂度比较高
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;

typedef pair<int ,int> pll;
const int N=100010;
int n,m;
int h[N],w[N],e[N],ne[N],idx;
int dist[N], cnt[N];//cnt记录步数，
bool st[N];

void add(int a,int b,int c){
    e[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx++;
}
//类似宽搜的方式
int spfa(){
    //不需要初始化了
    queue<int>q;
    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]){//如果已经在就不用再加了
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }
    return false;
}
int main(){
    scanf("%d%d",&n,&m);
    memset(h, -1, sizeof h);
    while(m--){
        int a,b,c;scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    if(spfa())puts("Yes");
    else puts("No");
    return 0;
}

#floyd

----c++版

https://www.acwing.com/problem/content/856/

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
//可以负权，不能负权回路
const int N=210, inf=1e9;
int n,m,Q;
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(){
    scanf("%d%d%d",&n ,&m ,&Q );
    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;
    while(m--){
        int a,b,w;scanf("%d%d%d",&a,&b,&w);
        d[a][b]=min(d[a][b],w);
    }
    
    floyd();
    
    while(Q--){
        int a,b;scanf("%d%d",&a,&b);
        if(d[a][b]>inf/2)puts("impossible");//非通路负权边的更新问题
        else printf("%d\n",d[a][b]);
    }
    return 0;
}

#prim

##Prim算法求最小生成树

----c++版

https://www.acwing.com/problem/content/860/

//朴素prim和dijkstra很像
//不同之处在于dijkstra是用t来更新其他点到起点的距离
//prim用t更新其他点到集合的距离
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=510, inf=0x3f3f3f3f;
int n,m;
int g[N][N];
int dist[N];//存到集合的距离
bool st[N];

int prim(){
    int res=0;
    memset(dist , 0x3f, sizeof dist);
    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(i&&dist[t]==inf)return inf;//不是第一个点了且距离inf，不存在
        if(i)res += dist[t];//先加再更新，不然有自负环的会出错把自己更新掉
        for(int j=1;j<=n;j++)dist[j]=min(dist[j], g[t][j]);        
        st[t]=true;
    }
    return res;
}

int main(){
    scanf("%d%d",&n,&m);
    memset(g, 0x3f, sizeof g);
    while(m--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        g[a][b]=g[b][a]=min(g[a][b], c);//建路连等式
    }
    int t=prim();
    if(t==inf)puts("impossible");
    else printf("%d",t);
    return 0;
}

#kruskal

稀疏图

##kruskal算法求最小生成树

----c++版

https://www.acwing.com/problem/content/861/

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
//由于要给边排序，o（mlogm），算法极限了。kruskal比较直接
//不需要存图，开个结构体存边就行
const int N=200010;
int n,m;
int p[N];
struct edge{
    int a,b,w;
    bool operator<(const edge &W)const{
        return w<W.w;
    }
}edges[N];

int find(int x){
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}//递归版

int main(){
    scanf("%d%d", &n,&m);
    for(int i=0;i<m;i++){
        int a,b,w;scanf("%d%d%d",&a,&b,&w);
        edges[i]={a,b,w};
    }
    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)puts("impossible");//注意边界
    else printf("%d", res);
    return 0;
}

#染色法判定二分图

----c++版

https://www.acwing.com/problem/content/862/

//二分图：可以把所有点划到两边，每边集合中没有边
//判断二分图，当且仅当图中不含奇数环（环的边数是奇数）
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e6+10,M=2000010;
int n,m;
int h[N],e[N],ne[N],idx;
int color[N];

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

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]){
            if(!dfs(j, 3-c))return false;
        }
        else if(color[j]==c)return false;
    }
    return true;
}

int main(){
    scanf("%d%d",&n,&m);
    memset(h, -1,sizeof h);
    while(m--){
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);add(b,a);
    }
    bool flag=true;
    for(int i=1;i<=n;i++)
        if(!color[i]){
            if(!dfs(i,1)){
                flag=false;
                break;
            }
        }
    
    if(flag)puts("Yes");
    else puts("No");
    return 0;
}

#匈牙利算法，二分图的最大匹配

----c++版

https://www.acwing.com/problem/content/863/

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=510,M=100010;
int n1,n2,m;
int h[N],e[M],ne[M],idx;
bool st[N];
int match[N];

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

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 main(){
    scanf("%d%d%d",&n1,&n2,&m);
    memset(h, -1, sizeof h);
    while(m--){
        int a,b;scanf("%d%d",&a,&b);
        add(a,b);//只用连一边的点的
    }
    int res=0;
    for(int i=1;i<=n1;i++){
        memset(st, false, sizeof st);
        if(find(i))res++;
    }
    printf("%d\n",res);
    return 0;
}

本文地址：https://blog.csdn.net/lafea/article/details/107558527