朴素Dijkstra // 单源汇正权边稠密图 求最短路 O(n^2)

#define int longlong
const int INF = 0x3f3f3f3f3f3f3f3f;

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

int dijkstra()
{
    // 起点初始化为0, 其他点初始化为无穷大(INF)
    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[t] > dist[j])) t = j;
        // 用t更新其他点
        for(int j = 1; j <= n; j++)
            dist[j] = min(dist[j], dist[t]+g[t][j]);
        // t已确定最短路 
        st[t] = true;
    }
    // 若为INF说明无路可通
    return dist[n] != INF ? dist[n] : -1;
}

堆优化Dijkstra // 单源汇正权边稀疏图 求最短路 O(mlogn)

#define int long long
#define PII pair<int,int>
const int INF = 0x3f3f3f3f3f3f3f3f;

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

void add(int x, int y, int v)
{
    e[idx] = y, w[idx] = v, ne[idx] = h[x];
    h[x] = idx ++;
}

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

    while(heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.second, d = 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] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
            }
        }
    }

    return dist[n] == INF ? -1 : dist[n];
}

Bellman-Ford // 单源汇有负边 求最短路 O(nm)

int n, m, k, dist[N], last[N];

struct Edge {
    int x, y, w;
} edge[M];

void bellman_ford()
{
    // dist数组初始化
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    // 最多经过不超过i条边时的最短路
    for(int i = 1; i <= k; i++)
    {
        // 复制原来的dist数组, 避免串联更新dist
        memcpy(last, dist, sizeof dist); 
        for(int j = 1; j <= m; j++)
        {
            auto e = edge[j];
            dist[e.y] = min(dist[e.y], last[e.x] + e.w);
        }
    }

    if(dist[n] > INF / 2) puts("impossible"); // 大于一个较大的值就说明不存在通路
    else printf("%lld\n", dist[n]);
}

SPFA // 单源汇有负边 求最短路 一般O(n) 最差O(nm)

int n, m, dist[N];
int h[N], e[N], w[N], ne[N], idx; 
bool st[N]; // 判断点是否在队列中

void spfa()
{
    // 初始化dist, 将起点入队
    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]可更新变小 --> 用j更新其他点
            {
                dist[j] = dist[t] + w[i];
                if(!st[j]) q.push(j), st[j] = true; // j不在队列中就入队
            }
        }
    }

    if(dist[n] == INF) puts("impossible"); // 无通路
    else printf("%lld\n", dist[n]);
}

SPFA // 单源汇有负边 判断是否存在负环 一般O(n) 最差O(nm)

int n, m;
int h[N], e[M], w[M], ne[M], idx;
int dist[N], cnt[N]; // cnt数组记录到点i的最短路经过多少条边
bool st[N];

bool spfa()
{
    queue<int> q;
    for(int i = 1; i <= n; i++) q.push(i), st[i] = 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];
                cnt[j] = cnt[t] + 1;
                if(cnt[j] >= n) return true; // 总共n个点, 经过>=n条边则必有负环
                if(!st[j]) q.push(j), st[j] = true;
            }
        }
    }
    return false;
}

Floyd // 多源汇求最短路 O(n^3)

int n, m, k;
int d[N][N]; // 邻接矩阵存图, 跑完floyd后d[i][j]表示i到j的最短距离

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]);
}

朴素Prim // 稠密图 求最小生成树 o(n^2)

int n, m, g[N][N], dist[N]; // 邻接矩阵存稠密图, dist数组表示点到集合中点的最短距离
bool st[N];

int prim()
{
    int res = 0;
    memset(dist, 0x3f, sizeof dist);
    for(int i = 0; i < n; i++)
    {
        int t = 0;
        for(int j = 1; j <= n; j++)
            if(!st[j] && (!t || dist[t] > dist[j])) t = j; // t是集合外中dist最小的点
        if(i && dist[t] == INF) return INF; // 除第一个点外, 若dist为INF说明无最小生成树
        if(i) res += dist[t]; // 除入集合的第一个点外, 累加边权
        st[t] = true; // 将点入集合
        for(int j = 1; j <= n; j++) dist[j] = min(dist[j], g[t][j]); // 用t更新未进入集合的点的dist
    }
    return res; // 返回累加的边权和
}

Kruskal // 稀疏图 求最小生成树 o(mlogm)

int n, m, fa[N]; // fa数组：并查集, 维护点集

struct Edge {
    int a, b, w;
    bool operator < (const Edge & W) const {
        return w < W.w;
    }
} e[M]; // 结构体数组存边

// 并查集中查找根节点的函数
int find(int x)
{
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

int kruskal()
{
    int res = 0, cnt = 0; // res：边权和, cnt：已连上的边数
    sort(e+1, e+1+m); // 将边按边权从小到大排序
    for(int i = 1; i <= n; i++) fa[i] = i; // 并查集初始化
    for(int i = 1; i <= m; i++)
    {
        int a = find(e[i].a), b = find(e[i].b);
        if(a != b) // a、b未连上
        {
            fa[a] = b; // 将点a、b连上
            res += e[i].w, cnt ++;
        }
        if(cnt == n-1) return res; // 最小生成树已求出
    }
    return INF; // 最小生成树不存在
}

染色法判二分图 o(n+m)

int n, m;
int h[N], e[M], ne[M], idx; // 邻接表存图
int color[N]; // 0表示未染色, 1、2为染的不同颜色

bool dfs(int u, int c)
{
    color[u] = c; // c表示染的颜色
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(!color[j] && !dfs(j, 3-c)) return false; // 若未染色, 对j及j可达的点进行染色, 3-c：染不同颜色
        else if(color[j] == c) return false; // 若j已染色, 但与u同色, 说明染色失败
    }
    return true; // 本次染色成功
}

bool stain()
{
    for(int i = 1; i <= n; i++)
        if(!color[i] && !dfs(i, 1)) return false; // 染色失败则不是二分图
    return true; // 所有点染色成功则为二分图
}

匈牙利算法 求二分图最大匹配 o(nm)

int n1, n2, m; // 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]) // 若j还未考虑过(避免重复考虑同一个点)
        {
            st[j] = true;
            if(!match[j] || find(match[j])) // 若该点未匹配 或 该点匹配的点可找到下家
            {
                match[j] = x; // x与j匹配上
                return true;
            }
        }
    }
    return false; // 未能为x找到匹配的点
}

int hungary() // 匈牙利算法
{
    int cnt = 0; // 最大匹配数
    for(int i = 1; i <= n1; i++)
    {
        memset(st, 0, sizeof st);
        if(find(i)) cnt ++; // 匹配成功则cnt+=1
    }
    return cnt;
}