基本的图论算法

图论是一位同级的计科老哥做的介绍，简单的总结一下他上课提到的这些图论算法以及问题。大概这也就是差不多要准备的模板吧，下面是自己总结的他的一个思路，本文也会根据这个思路来组织内容：

最小生成树

定义补足

Prim 算法

Kruskal 算法

题型

树形DP

LCA /倍增

最短路问题

最短路算法应该是整个图论算法体系中使用的最频繁的一类算法吧，大体就是有三种比较常见的算法，它们有各自的特点，但是一般使用是后两者居多。为了熟悉这三个算法大概我是写了洛谷P3371这个题目，分别使用了这三种方法来写。

Floyd 算法

Dijkstra 算法

SPFA 算法

强连通和双连通

二分图匹配

~~这一部分的东西看之前的代码渐渐魔怔了~~

匈牙利算法

说这个之前先提一下二分图的一个性质：

König定理：
二分图中，最小覆盖点数 = 最大匹配数。这里的最小点覆盖指的是，对于二分图找到最少的一些点，使二分图所有的边都至少有一个端点在这些点之中。或者说，只要删除包含这些点的边，可以删掉所有边，这个点集就是最小点覆盖。

匈牙利算法是使用寻找增广路的方法来解决二分图最大匹配问题的算法。简单的说就是有一个二分图，假设两侧点集为M和N。然后先尽可能匹配M和N里的点，如果遇到冲突的话就DFS，让原配去寻找其它的可能性（）也就是增广路。找到了，大家Happy*Happy，匹配数喜加一；找不到，再见==

最简单的板子大概就长下面这样。主要是nextMatch也就是DFS和对每一个点发起匹配的maxMatch函数构成，不太要求存图方法，下面用的是邻接矩阵。然后得到结果的同时还会得到一个最大匹配的方案。

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1050;     // u <= n
const int M = 1050;     // v <= M

int n,m,e,u,v;
bool graph[N][M]{0};    
bool visit[M]{0};       // v是否被访问
int match[M]{0};        // match[v]=u;

bool nextMatch(int i)   // 其实这是DFS
{
    for(int j=1;j<=m;++j)   // 不要从中途开始
        if(graph[i][j]&&!visit[j])
        {
            visit[j] = true;
            if(!match[j]||nextMatch(match[j]))
            {
                match[j] = i;
                return true;
            }
        }
    return false;
}

inline int maxMatch()
{
    int ans = 0;
    for(int i=1;i<=n;++i)   // 要重置visit
    {
        memset(visit,0,sizeof(bool)*(m+1));
        if(nextMatch(i)) ++ans;
    }
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>n>>m>>e;
    while(e--)
    {
        cin>>u>>v;
        graph[u][v] = true;
    }
    cout<<maxMatch()<<endl;

    return 0;
}

这个板子是基于洛谷P3386来写的。细节方面有两点要注意：一是因为递归链调用累计，所以必须要有visit数组，而且每次还要复位；二就是寻找增广路时，之前扫过的部分不可跳过。