模板（二）

DFS 深度优先搜索

1
2
3
4
void dfs(int u)
{
    if(u==n)    //pd[u] 表示点u已经被遍历过
    {
}     

for (```)
{
    if(```)
    {
        
1
2
3
4
            dfs(u+1);
        }
    }
}

树的 DFS

1
2
3
4
5
6
7
8
9
10
int dfs(int u)
{
    pd[u] = true; // pd[u] 判断点u已经被遍历过

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

BFS 宽度优先搜索

1
2
void bfs(int a,int b)
{
q.push({a,b});
while (!q.empty())
{
    for(```)
    {
        if(```)
        {
            
1
2
3
4
5
                q.push({x,y});
            }
        }
    }
}

拓扑排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
bool topsort()
{
    for(int i=1;i<=n;i++)
    {
        if(d[i]==0)
        {
            q.push(i);
        }
    }
    while (!q.empty())
    {
        int t=q.front();
        q.pop();
        ans[k++]=t;
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            d[j]--;
            if(d[j]==0)
            {
                q.push(j);
            }
        }
    }
    return k==n;
}

最短路问题

$n:$点 $m:边$

Dijkstra-朴素 $O(n^2+m)$

  1. 初始化距离数组, dist[1] = 0, dist[i] = inf;
  2. for n次循环 每次循环确定一个min加入S集合中，n次之后就得出所有的最短距离
  3. 将不在S中dist_min的点->t
  4. t->S加入最短路集合
  5. 用t更新到其他点的距离

Dijkstra-堆优化 $O(mlogm)$

  1. 利用邻接表，优先队列
  2. 在priority_queue<PII,vector<PII>,greater<PII>> heap;中将返回堆顶
  3. 利用堆顶来更新其他点，并加入堆中类似宽搜

Bellman_ford $O(nm)$

  1. 注意连锁想象需要备份, struct Edge{int a,b,c} Edge[M];
  2. 初始化dist, 松弛 dist[x.b] = min(dist[x.b], backup[x.a]+x.w);
  3. 松弛k次，每次访问m条边

Spfa $O(n) ~ O(nm)$

  1. 利用队列优化仅加入修改过的地方
  2. for k次
  3. for 所有边利用宽搜模型去优化bellman ford算法
  4. 更新队列中当前点的所有出边

Floyd $O(n^3)$

  1. 初始化d
  2. k, i, j 去更新d

朴素 dijkstra $O(n^2+m)$

  • 不能有负权边

  • 用邻接矩阵 $g$ 表示点和点的关系

    g[i][j] 表示点 $i$ 和点 $j$ 之间的边权

  • 当 $m$ 为 $n^2$ 数量级的时候用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
bool pd[N];
int dist[N];        //存放最短距离
int g[N][N];        // g[x][y] 表示x到y的距离
int n,m;

void 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(!pd[j]&&(t==-1||dist[t]>dist[j]))    //找出最小的dist
            {
                t=j;
            }
        }

        pd[t]=true;

        for(int j=1;j<=n;j++)
        {
            dist[j]=min(dist[j],dist[t]+g[t][j]);
        }
    }
}

堆优化版 dijkstra $O(mlogn)$

  • 不能有负权边

  • $m<n^2$ 时用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
void add(int a,int b,int c)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx;
    w[idx]=c;       // a到b的边权
    idx++;
}

void dijkstra(int u)
{
    memset(dist,0x3f,sizeof(dist));
    priority_queue<PII,vector<PII>,greater<PII>> heap;
    dist[u]=0;
    heap.push({0,u});

    while (!heap.empty())
    {
        auto t=heap.top();          //先在已知路径里面选出最短路径
        heap.pop();
        int distance=t.first;
        int ver=t.second;

        if(pd[ver]) continue;
        pd[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});
            }
        }
    }
}

Bellman-Ford 算法 $O(nm)$

  • 可以有负权边

  • 解决有边数限制的最短路问题（如最多走k条边）

  • 当边循环i次时，表示最多走i条边的最短路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
struct Node
{
    int a;
    int b;
    int w;
}edge[M];       //存边

int dist[N];
int backup[N];

void bf(int u)
{
    memset(dist,0x3f,sizeof(dist));
    dist[u]=0;          //从u点开始

    for(int i=0;i<k;i++)
    {
        memcpy(backup,dist,sizeof(dist));   //防止后面循环里更新数据时用的是已经更新过的新数据
        for(int j=0;j<m;j++)        //循环松弛每条边
        {
            int a=edge[j].a,b=edge[j].b,w=edge[j].w;
            dist[b]=min(dist[b],backup[a]+w);
        }
    }
}

int main()
{
    int a,b,w;
    cin>>n>>m>>k;
    for(int i=0;i<m;i++)
    {
        cin>>a>>b>>w;
        edge[i]={a,b,w};        //a到b边权为w（可以为负）
    }
    bf(1);
    if(dist[n]>0x3f3f3f3f/2)  cout<<"impossible"<<endl<<endl;
    else    cout<<dist[n]<<endl;
    return 0;
}

SPFA 算法 $O(m) ~ O(nm)$

  • 可以有负权边

  • 某点变小了才会让后续节点继续变小

    so 变小节点入队

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
void add(int a,int b,int c)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx;
    w[idx]=c;
    idx++;
}

void spfa(int u)
{
    memset(dist,0x3f,sizeof(dist));
    queue<int> q;
    dist[u]=0;
    q.push(u);
    pd[u]=true;
    while (!q.empty())
    {
        int t=q.front();
        q.pop();
        pd[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(!pd[j])
                {
                    pd[j]=true;
                    q.push(j);
                }
            }
        }
    }
}

spfa 判断图中是否存在负环

因为点1可能到不了有负环的点， 因此把所有点都加入队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
bool pd[N];
int h[N],e[N],ne[N],w[N],idx;
int dist[N];
int cnt[N];     // cnt 记录路径长度
int n,m;

bool spfa()         
{           
    queue<int> q;           //不用memset(dist,0x3f,dist)
    for(int i=1;i<=n;i++)   //全部入队而不是某个点入队，因为判断的是整张图有无负环
    {
        q.push(i);
        pd[i]=true;
    }

    /*如果题目问的是从顶点1出发能到达的负环，就要用下方代码

    memset(dist,0x3f,sizeof(dist));
    dist[1]=0;
    q.push(1);
    pd[1]=true;

    */

    while (!q.empty())
    {
        int t=q.front();
        q.pop();
        pd[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(!pd[j])
                {
                    pd[j]=true;
                    q.push(j);
                }
            }
        }
    }
    return false;       //无负环
}

floyd 算法 $O(n^3)$

多源最短路算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//先初始化，再输入邻接矩阵
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;
    }
}

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]);
            }
        }
    }
}   //d[i][j]表示从i到j的最短距离

最小生成树

prim 算法 $O(n^2)$

可类比朴素 $dijkstra$ 算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
bool prim(int u)
{
    memset(dist,0x3f,sizeof(dist));
    dist[u]=0;

    for(int i=0;i<n;i++)
    {
        int t=-1;
        for(int j=1;j<=n;j++)
        {
            if(!pd[j]&&(t==-1||dist[t]>dist[j]))
            {
                t=j;
            }
        }

        if(dist[t]==INF)    return false;   //孤立点，无最小生成树

        pd[t]=true;
        ans+=dist[t];

        for(int j=1;j<=n;j++)
        {
            dist[j]=min(dist[j],g[t][j]);
        }
    }
    return true;
}

kruskal 算法 $O(mlogm)$

先把边按照权重排序

再从小到大枚举，如果这条边不在生成树中，则加上这条边（用并查集）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool kruskal()
{
    sort(edge,edge+m,cmp);

    for(int i=0;i<m;i++)
    {
        int a=edge[i].a,b=edge[i].b,w=edge[i].w;
        int pa=find(a),pb=find(b);  // a、b 点所在的集合
        if(pa!=pb)
        {
            p[pa]=pb;       //合并a，b所在集合
            ans+=w;
            cnt++;
        }
    }

    if(cnt==n-1)    return true;    //边数如果=点数-1，则存在最小生成树
    else    return false;
}

二分图

（就是二部图…）

  • 当且仅当图中无奇数环

染色法判断二分图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
bool dfs(int u,int c)   //只要染色出问题了，就返回false
{
    colour[u]=c;

    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!colour[j])
        {
            if(!dfs(j,3-c))
            {
                return false;
            }
        }else if(colour[j]==c)
        {
            return false;
        }
    }
    return true;
}


    pd=1;
    for(int i=1;i<=n;i++)   //进行逐个染色
    {
        if(!colour[i])
        {
            if(!dfs(i,1))
            {
                pd=0;
            }
        }
    }
    if(pd)
    cout<<"Yes"<<endl;
    else
    cout<<"No"<<endl;

匈牙利算法 $O(m∗n)$

  • 前提是二分图

  • 找到最大匹配（即最多有几对 “ 一对一 ”）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
bool find(int u)
{       
    for(int i=h[u];i!=-1;i=ne[i])   //遍历该点连接的右侧的点
    {
        int j=e[i];
        if(!pd[j])
        {
            pd[j]=true;

            if(!match[j]||find(match[j]))
            {
                match[j]=u;
                return true;
            }
        }
    }

    return false;
}


    for(int i=1;i<=n1;i++)  //去匹配每个左边的点
    {
        memset(pd,false,sizeof(pd));    //每次都变为false，判断每次find时已经被选择的右侧的点

        if(find(i)) ans++;
    }