图论

(1)最短路模型:

基础模型：
朴素dijkstra、dijkstra堆优化、Bellman-Ford、SPFA
（注：正权边最好不要用SPFA算法，因为它会被卡）

1.朴素dijkstra：

适用于正权边，时间复杂度 $O(n^2)$
dijkstra求最短路I

2.堆优化dijkstra：

在考虑dijkstra时，如果用二叉堆进行求解
$O(log n)$ 的时间寻找最小值
$O(log n)$ 的时间拓展每一条邻边

总共时间复杂度 $O(m log n)$

堆优化dijkstra

3.Bellman-Ford:

适用于有边数限制的负权边图 时间复杂度 $O(n*m)$

一共循环n次，每次在上一次的基础上，用每条边的边权优化

Bellman-Ford

4.SPFA：

在Bellman-Ford的过程中，因为只有连向这个点的某一个点优化了，
这个点才会跟着优化，所以每次只要枚举这个点的所有出边，
在对于每一个指向的点进行优化、入队就能解决像Bellman-Ford一样的题
时间复杂度 $O(m)~O(nm)$,因为可能被卡成O(nm),所以正权边不要用SPFA
比如这题：新年好
SPFA负权边最短路

(2)多源最短路Floyd：

暴力出奇迹，时间复杂度 $O(n^3)$
相当于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]);
}

(3)最小生成树：

给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环，边权可能为负数。

求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。

给定一张边带权的无向图 G=(V,E)，其中 V 表示图中点的集合，E 表示图中边的集合，n=|V|，m=|E|。

由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一棵生成树，
其中边的权值之和最小的生成树被称为无向图 G 的最小生成树。

视频讲解。。。。

Prim：

int prim()
{
    int res=0;
    for(int i=0;i<n;i++)
    {
        int pos=0;
        for(int j=1;j<=n;j++)
            if(!st[j]&&(pos==0||d[j]<d[pos]))
                pos=j;

        st[pos]=1;
        if(i&&d[pos]==INF)return INF;
        if(i)res+=d[pos];

        for(int j=1;j<=n;j++)d[j]=min(d[j],g[pos][j]);
    }

    return res;
}

Kruskal：

#include<bits/stdc++.h>
using namespace std;
const int N=200010;
int n,m;
struct node{
    int u,v,w;
}edge[N];
int p[N];
bool cmp(node a,node b)
{
    return a.w<b.w;
}
int find(int x)
{
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}
int Kruskal()
{
    int res=0,cnt=0;
    for(int i=0;i<m;i++)
    {
        int a=edge[i].u;
        int b=edge[i].v;
        int c=edge[i].w;
        if(find(a)!=find(b))
        {
            p[find(a)]=p[find(b)];
            cnt++;
            res+=c;
        }
    }

    if(cnt==n-1)return res;
    return 0x3f3f3f3f;
}
int main()
{
    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++)p[i]=i;

    for(int i=0;i<m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        edge[i]=node{a,b,c};
    }

    sort(edge,edge+m,cmp);

    int ans=Kruskal();

    if(ans==0x3f3f3f3f)printf("impossible");
    else printf("%d",ans);

    return 0;
}

(3)二分图

1.二分图的判定（染色法）：

bool bfs(int st,int c)
{
    queue<PII> q;
    q.push({st,c});
    color[st]=c;
    used[st]=1;
    while(q.size())
    {
        PII t=q.front();
        q.pop();

        int u=t.first,p=t.second;

        for(int i=h[u];~i;i=ne[i])
        {
            int v=e[i];
            if(used[v]&&color[v]==p)return false;
            if(!used[v])
            {
                used[v]=1;
                color[v]=1-p;
                q.push({v,color[v]});
            }
        }
    }

    return true;
}

2.匈牙利算法二分图最大匹配

匈牙利算法

int find(int u)
{
    memset(st,0,sizeof st);

    for(int i=h[u];~i;i=ne[i])
    {
        int v=e[i];
        if(st[v])continue;

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

    return false;
}

感谢资瓷！！！