算法笔记03

排列数字（DFS）

使用DFS进行排列（回溯），递归

#include<iostream>
using namespace std;
const int N=10;
int path[N],n;//存储状态
bool st[N];
void dfs(int u){
    if(u==n){//走到第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(){
    cin>>n;
    dfs(0);
    return 0;
}

走迷宫（BFS）

优势：搜到最短路

最短路<–>Dp问题

#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int,int> PII;//利用stl的队列
int n,m;
const int N=110;
int g[N][N],d[N][N];//g地图；d：每一个点到起点的距离
PII q[N*N];
int bfs(){
    int hh=0,tt=0;
    memset(d,-1,sizeof(d));//表示没有走过
    d[0][0]=0;//表示第一个点已经走过了
    q[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]=1+d[t.first][t.second];
            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()<<endl;
    return 0;
}

图的遍历

DFS：一条路走到死

BFS：所有距离的点依次搜索出来

int dfs(int u){
    st[u]=true;//标记已经被搜索过了
    int size=0,sum=0;
    for(int i=h[u];i!=-1;i=ne[i]){//遍历所有出边
        int j=e[i];
        if(!st[j]) dfs(j);
    }
}

题目：

给定一颗树，树中包含 n 个结点（编号 1∼n）和 n−1 条无向边。

请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。

重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N=100010,M=N*2;
int n;
int h[N],e[M],ne[M],idx;
int ans=N;//答案，最小的最大值
bool st[N];
void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
int dfs(int u){//以u为根的子树的大小
    st[u]=true;//标记已经被搜索过了
    int size=0,sum=0;
    for(int i=h[u];i!=-1;i=ne[i]){//遍历所有出边
        int j=e[i];
        if(st[j]) continue;
        int s=dfs(j);
        size=max(size,s);
        sum+=s;
    }
    size=max(size,n-sum-1);//求删除后子连通图的最大值
    ans=min(size,ans);//答案取最小
    return sum+1;
}
int main()
{
    memset(h,-1,sizeof(h));
    scanf("%d",&n);
    for(int i=0;i<n-1;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b),add(b,a);//无向边，需要加入两条
    }
    dfs(1);
    printf("%d\n",ans);
    return 0;
}

BFS（所有长度都是1）

#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N=100010;
int h[N],e[N],ne[N],idx;
int d[N],q[N];//距离、队列
int st[N];
int n,m;
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!=0;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;
        scanf("%d%d",&a,&b);
        add(a,b);
    }
    cout<<bfs()<<endl;
    return 0;
}

有向图的拓扑排序（BFS应用）

注意：有向图才有拓扑序列

拓扑序列：对于同样的起点和终点，不管怎么走，起点永远在终点的前面

#include<iostream>//答案不唯一
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100010;
int q[N],d[N],h[N],e[N],ne[N],idx;//邻接表的存储方式，q：入度
int n,m,tt=-1,hh=0;
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void topsort(){
    for(int i=1;i<=n;i++){
        if(d[i]==0) q[++tt]=i;
    }
    while(hh<=tt){
        int a=q[hh++];
        for(int i=h[a];i!=-1;i=ne[i]){
            int b=e[i];
            d[b]--;
            if(d[b]==0){//b入读为0
                q[++tt]=b;
            }
        }
    }
    if(tt==n-1){//存在拓扑序列，一共进了n个点
        for(int i=0;i<n;i++){
            printf("%d ",q[i]);
        }
    }
    else cout<<"-1";
}
int main(){
    cin>>n>>m;
    memset(h,-1,sizeof h);
    while(m--){
        int a,b;
        cin>>a>>b;
        add(a,b);
        d[b]++;//b的入读增加
    }
    topsort();
    return 0;
}

Dijkstra

朴素版的Dijkstra（有向图）

1. 初始化：dist[1]=0,dist[i]=+∞（用一个很大的数代替即可）
   s：当前已经确定了最短距离的点

2. for(i=0;i<n;i++){//每次找到距离最小的点，然后用这个点更新剩下点到
       t<-不在s中的距离最近的点
       s<-t
       (if(dist[x]>dist[t]+w)//用t更新其他所有点的距离
   }
   3. 求时间复杂度：O(n^2^)
   
   4. 稠密图：用邻接矩阵存储
      稀疏图：用邻接表存储
   
      ---
   
   
   ```C++
   #include<iostream>//dijkstra算法不支持负权边
   #include<cstring>
   #include<algorithm>
   using namespace std;
   const int N=520;
   int m,n;
   int dist[N],g[N][N];//距离，地图
   bool st[N];//每个点是否已确定
   int dijkstra(){
       memset(dist,0x3f,sizeof dist);//初始化距离为+∞
       dist[1]=0;
       for(int i=1;i<=n;i++){
       int t=-1;
           for(int j=1;j<=n;j++){
               if(!st[j]&&(t==-1||dist[j]<dist[t])) t=j;
           }//找到所有没确定的点中的距离的最小值
           st[t]=true;
       for(int j=1;j<=n;j++){
           dist[j]=min(dist[j],dist[t]+g[t][j]);
       }//用t更新距离
       }
       if(dist[n]==0x3f3f3f3f) return -1;//1、n不连通
       else 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);//读入m条边
           g[a][b]=min(g[a][b],c);//重边只保留长度最短的
       }
       int t=dijkstra();
       printf("%d",t);
       return 0;
   }
   

堆优化版的dijkstra算法

在每次寻找没被纳入的点中距离最短的点的时候，使用堆优化，把这一步的时间复杂度从m变成1

手写堆：可以实现修改任意值（映射）
优先队列：不支持任意修改元素 O(mlogn)

#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;
const int N=150010;
int n,m;
int dist[N],e[N],w[N],ne[N],idx,h[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 dijkstra(){
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    priority_queue <PII,vector<PII>,greater<PII>> heap;
    heap.push({0,1});//1号点已经知道最短距离了，是0
    while(heap.size()){
        auto t=heap.top();//每次找到距离最小的点
        heap.pop();//最多只有m条边
        int ver=t.second;
        if(st[ver]) continue;//这个点之前出现过
        st[ver]=true;
        for(int i=h[ver];i!=-1;i=ne[i]){//遍历所有临边
            int j=e[i];
            if(dist[j]>dist[ver]+w[i]){
                dist[j]=dist[ver]+w[i];
                heap.push({dist[j],j});
            }
        }
    }
    if(dist[n]==0x3f3f3f3f) return -1;
    else 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();
    cout<<t<<endl;
    return 0;
}

Bellman-Ford算法

for n次迭代
	for 所有边
	备份，防止边数限制
		for 所有边a,b,w
		dist[b]=min(dist[b],dist[a]+w)//循环完之后，对于多有的边，一定满足dist[b]≤dist[a]+w（三角不等式），松弛操作，不能有负权回路->不超过k条边

#include<iostream>//Bellman-Ford算法可以用来寻找负环，因为如果边数>n,证明最短路径有n+1个点，因此存在负环
#include<cstring>//适用于限制边数的路径
#include<algorithm>
using namespace std;
const int N=510;
int dist[N],last[N],m,n,k;
struct{
    int a,b,w;//边的起点、终点、权重
}edges[10010];
void bellman_ford(){
    memset(dist,0x3f,sizeof dist);//初始化
    dist[1]=0;
    for(int i=0;i<k;i++){
        memcpy(last,dist,sizeof dist);//备份dist数组，只用上一次更新的结果来更新
        for(int j=0;j<m;j++){
            auto e=edges[j];
            dist[e.b]=min(last[e.a]+e.w,dist[e.b]);
        }
    }
    if(dist[n]>0x3f3f3f3f/2) puts("impossible");防止出现0x3f3f3f3f-1这种
    else cout<<dist[n];
}
int main(){
    cin>>n>>m>>k;
    for(int i=0;i<m;i++){
        cin>>edges[i].a>>edges[i].b>>edges[i].w;
    }
    bellman_ford();
    return 0;
}

spfa算法

求最短路

要求不含负环

for n次迭代
	for 所有边
	备份，防止边数限制
		for 所有边a,b,w
		dist[b]=min(dist[b],dist[a]+w)//优化：只有dist[a]变化时，才需要更新dist[b]

每一次先把起点放到队列，只要队列不空，每一次有边变小时：

1. t<-q.front取出队头
   q.pop()
2. 更新t的所有出边
   • queue<-b

#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int N=100010;
int dist[N],m,n,e[N],ne[N],h[N],w[N],idx;
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]){//更新t的所有邻边
            int j=e[i];
            if(dist[j]>dist[t]+w[i]){
                dist[j]=dist[t]+w[i];
                if(!st[j]){//如果j不在队列里面采访进去
                    st[j]=true;
                    q.push(j);
                }
            }
        }
    }
    return dist[n];
}
int main(){
    cin>>n>>m;
    memset(h,-1,sizeof h);
    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }
    int t=spfa();
    if(t==0x3f3f3f3f) puts("impossible");
    else printf("%d",dist[n]);
    return 0;
}

Floyd算法

求多元最短路

d[i,j]：存储所有边

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

不存在负权回路（最短距离会变成-∞）

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=210;
int INF=1e9,m,n,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(){
    scanf("%d%d%d",&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;
        }
    }
    while(m--){
        int x,y,z;
        cin>>x>>y>>z;
        d[x][y]=min(d[x][y],z);
    }
    floyd();
    while(k--){
        int a,b;
        cin>>a>>b;
        if(d[a][b]>INF/2) cout<<"impossible"<<endl;
        else cout<<d[a][b]<<endl;
    }
    return 0;
}

Prim算法

朴素版

初始化所有距离为+∞
for(i=0;i<n;i++){
	t<-找到不在集合中的距离最小的点（集合：连通块）
	用t更新其他点到集合的距离//dijkstra：更新的是其他点到起点的距离
	st[t]=true
}

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=510,INF=0x3f3f3f3f;
int n,m,g[N][N],dist[N];//稠密图，用邻接矩阵存储
bool st[N];
int prim(){
    memset(dist,INF,sizeof dist);//初始化所有距离
    int res=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=-1：当前没有找到任何点
                t=j;
            }
        }
        st[t]=true;
        if(i&&dist[t]==INF) return INF;
        if(i) res+=dist[t];//只要不是第一个点，就把距离加上
        for(int j=1;j<=n;j++){//用t更新其他店的距离
            dist[j]=min(dist[j],g[t][j]);//先累加在更新，不然自环距离会变成负值
        }
    }
    return res;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j) g[i][j]=0;
            else g[i][j]=INF;
        }
    }
    int u,v,w;
    while(m--){
        cin>>u>>v>>w;
        g[v][u]=g[u][v]=min(g[u][v],w);//无向图
        
    }
    int t=prim();
    if(t>INF/2) puts("impossible");
    else cout<<t<<endl;
    return 0;
}

Kruskal算法

将所有边按照权重从小到大排序（可以用快排）0（mlogm）
枚举每条边a,b，权重为c
    if(a,b)不连通
    	将这条边加入集合

#include<iostream>//稀疏图一般用kruskal
#include<algorithm>
using namespace std;
const int N=200010;
int m,n,p[N],res,cnt;
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 kruskal(){
    for(int i=0;i<m;i++){//从小到大枚举所有边
        int a=edges[i].a,b=edges[i].b,w=edges[i].w;
        if(find(a)!=find(b)){
            p[find(a)]=p[find(b)];
            res+=w;
            cnt++;//当前加入多少条边
        }
    }
    if(cnt==n-1){
        return res;
    }
    else return 0x3f3f3f3f;
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++) p[i]=i;//初始化并查集
    for(int i=0;i<m;i++){
        cin>>edges[i].a>>edges[i].b>>edges[i].w;
    }
    sort(edges,edges+m);
    int t=kruskal();
    if(t==0x3f3f3f3f) puts("impossible");
    else cout<<t;
    return 0;
}

二分图

染色法

一个图是二分图，当且仅当图中不含奇数环

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100010,M=200010;
int h[N],e[M],ne[M],n,m,idx,color[N];
void add(int a,int b){//邻接表存储图
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
bool dfs(int x,int c){
    color[x]=c;
    for(int i=h[x];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(){
    cin>>n>>m;
    memset(h,-1,sizeof h);
    while(m--){
        int a,b;
        cin>>a>>b;
        add(a,b),add(b,a);//加两编
    }
    bool flag=true;
    for(int i=1;i<=n;i++){
        if(!color[i]){//只要i没有遍历，就深度优先搜索便利
            if(!dfs(i,1)){
                flag=false;
                break;
            }
        }
    }
    if(!flag) puts("No");
    else puts("Yes");
    return 0;
}

二分图的最大匹配

匈牙利算法：再比较快的时间内告诉我们左右两边最大的匹配成功数

时间复杂度：O(n*m) 最坏情况

#include<iostream>
#include<cstring>
using namespace std;
const int N=510,M=100010;
int h[N],e[M],n1,n2,m,res,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(0==match[j]||find(match[j])){//如果没有匹配过或者可以给他找到下家
                match[j]=x;
                return true;
            }
        }
    }
    return false;
}
int main(){
    cin>>n1>>n2>>m;//左边n1个点，右边n2个点
    memset(h,-1,sizeof h);
    while(m--){
        int a,b;
        cin>>a>>b;
        add(a,b);
        
    }
    for(int i=1;i<=n1;i++){
        memset(st,false,sizeof st);//所有妹子清空
        if(find(i)) res++;
    }
    cout<<res<<endl;
    return 0;
}