最小生成树数——prim算法O(n^2)：
用途：求最小生成树的稠密图时
prim 算法干的事情是：给定一个无向图，在图中选择若干条边把图的所有节点连起来。要求边长之和最小。在图论中，叫做求最小生成树。
prim 算法采用的是一种贪心的策略。
每次将离连通部分的最近的点和点对应的边加入的连通部分，连通部分逐渐扩大，最后将整个图连通起来，并且边长之和最小。
prim与dijkstra联系：
prim中dist用来存储各个节点到生成树的最短距离，dijkstra中dist用来存储各个节点到源点的最短距离
1 #include <iostream>
2 #include <cstring>
3
4 using namespace std;
5
6 const int N=510,INF=0x3f3f3f3f;
7 int res,n,m;
8 int dist[N]; //存储各个节点到生成树的最短距离
9 int pre[N]; //各个节点的前去节点
10 int g[N][N];
11 bool st[N]; //判断节点是否被加入到生成树里
12
13 void prime()
14 {
15 memset(dist,0x3f,sizeof dist);
16 for(int i=0;i<n;i++)
17 {
18 int t=-1;
19 for(int j=1;j<=n;j++)//找不在连通块中且到连通块中某点的距离最近的点
20 {
21 if(!st[j]&&(t==-1||dist[j]<dist[t]))t=j;
22 }
23
24 if(i&&dist[t]==INF) //如果连通块中有点，但是找到的dist仍是inf
25 { //说明存在不连通的点，则不存在最小生成树
26 res=INF;
27 break;
28 }
29 if(i)res+=dist[t]; //第一次循环的时候，dist[0]=inf
30 //此时连通块只有一个点，距离为0
31 st[t]=1; //说明t点已被加入到生成树里，但不一定此时dist[t]最小
32
33 for(int j=1;j<=n;j++) //用t更新其他点的距离（不管在不在连通块里）
34 {
35 if(dist[j]>g[t][j])
36 {
37 dist[j]=g[t][j];
38 pre[j]=t; //从t到j的距离更短，j的前驱变为t
39 }
40 }
41 }
42
43 }
44
45 void path()//输出各条边
46 {
47 for(int i=n;i>1;i--)printf("%d %d\n",i,pre[i]);
48
49 }
50
51 int main()
52 {
53 scanf("%d%d",&n,&m);
54 memset(g,0x3f,sizeof g);
55 while(m--)
56 {
57 int u,v,w;
58 scanf("%d%d%d",&u,&v,&w);
59 g[u][v]=g[v][u]=min(g[u][v],w); //无向图
60 }
61
62 prime();
63 path();
64
65 if(res==INF)puts("impossible");
66 else printf("%d\n",res);
67
68
69
70 return 0;
71 }
最小生成树数——kruskal算法O(mlogm)：
用途：最小生成树的稀疏图
做法：1.将边和边权放入结构体里，按边权从小到大排序。
2.将n个点初始化为并查集的祖宗节点
3.对m条边循环，如果两点不在同一集合里，则合并集合，并将边权求和，边数++
4.如果边数最终不等于n-1，说明构不成最小生成树。反之则输出边权和
1 #include <iostream>
2 #include <algorithm>
3 using namespace std;
4
5 const int M=2e5+10;
6 int p[M],cnt,res; //cnt表示集合中的边数，res表示权重之和
7 int n,m;
8 struct EDGE
9 {
10 int a,b,w;
11 bool operator<(const EDGE &W)const
12 {
13 return w<W.w;
14 }
15 }edges[M];
16
17 int find(int x) //并查集找祖宗节点
18 {
19 if(p[x]!=x)p[x]=find(p[x]);
20 return p[x];
21 }
22
23 void kruskal()
24 {
25 sort(edges,edges+m); //每条边权重从小到大排序
26 for(int i=1;i<=n;i++)p[i]=i; //并查集祖宗节点赋值
27
28 for(int i=0;i<m;i++)
29 {
30 int a=edges[i].a,b=edges[i].b, w=edges[i].w;
31 if(find(a)!=find(b)) //如果a、b所在集合不是同一个集合，就合并
32 {
33 p[find(b)]=find(a);
34 cnt++;
35 res+=w;
36 }
37 }
38 }
39
40 int main()
41 {
42 scanf("%d%d",&n,&m);
43 for(int i=0;i<m;i++)
44 {
45 int u,v,w;
46 scanf("%d%d%d",&u,&v,&w);
47 edges[i]={u,v,w};
48 }
49
50 kruskal();
51 if(cnt!=n-1)puts("impossible");
52 //如果集合中边数不够n-1条，说明所有的点没连起来，没有最小生成树
53 else printf("%d\n",res);
54
55
56 return 0;
57 }
二分图——染色法O(m+n)：
二分图：
将所有点分成两个集合，使得所有边只出现在集合之间，就是二分图
二分图：一定不含有奇数环，可能包含长度为偶数的环， 不一定是连通图
思路dfs：
染色可以使用1和2区分不同颜色，用0表示未染色
遍历所有点，每次将未染色的点进行dfs, 默认染成1或者2
由于某个点染色成功不代表整个图就是二分图,因此只有某个点染色失败才能立刻break/return
染色失败相当于存在相邻的2个点染了相同的颜色
1 #include <iostream>
2 #include <cstring>
3 using namespace std;
4
5 const int N=2e5+10;
6 int n,m;
7 int h[N],ne[N],e[N],idx;
8 int color[N]; //0代表没涂色，1代表涂成红色，2代表涂成蓝色
9
10 void add(int a,int b)
11 {
12 e[idx]=b;ne[idx]=h[a];h[a]=idx++;
13 }
14
15 bool dfs(int t,int p)
16 {
17 color[t]=p; //将t点涂成p
18 for(int i=h[t];i!=-1;i=ne[i]) //在和点t相连的各点中搜索
19 {
20 int j=e[i];
21 if(!color[j]) //如果j点没有涂色
22 {
23 if(dfs(j,3-color[t])==0)return 0;
24 //当j涂成与t相反的颜色时，有重复色 ，则失败
25 }
26 else if(color[j]==color[t])return 0;
27 //如果j涂色和t一样，有重复色，失败
28 }
29 return 1;
30 }
31
32 int main()
33 {
34 scanf("%d%d",&n,&m);
35 memset(h,-1,sizeof h);
36 for(int i=1;i<=m;i++)
37 {
38 int u,v;
39 scanf("%d%d",&u,&v);
40 add(u,v);add(v,u); //无向图
41 }
42
43 bool flag=1;
44 for(int i=1;i<=n;i++)
45 {
46 if(!color[i]&&!dfs(i,1)) //如果i没有涂色，并且搜索之后有涂色矛盾
47 { //则失败
48 flag=0;
49 break;
50 }
51
52 }
53
54 if(flag)puts("Yes");
55 else puts("No");
56
57
58
59 return 0;
60 }
二分图——匈牙利算法O(m*n)：
用途：求二分图的最大匹配数
#include <iostream>
#include <cstring>
using namespace std;
const int M=1e5+10,N=510;
int h[N],ne[M],e[M],idx;
int n1,n2,m,res;
bool st[N];
int match[N];
void add(int a,int b) //男对女，不需要女对男
{
ne[idx]=h[a];e[idx]=b;h[a]=idx++;
}
bool find(int u)
{
for(int i=h[u];i!=-1;i=ne[i]) //遍历所有自己喜欢的女生
{
int j=e[i];
if(!st[j]) //如果这个女生在这一轮还没被预约
{
st[j]=1; //这个男生就预约了
if(!match[j]||find(match[j]))
{ //如果女生没有男朋友或者她男朋友能再从喜欢的女生中找一个女朋友
match[j]=u; //这个女生就和u在一起了
return 1; //匹配成功
}
}
}
return 0;
}
int main()
{
scanf("%d%d%d",&n1,&n2,&m);
memset(h,-1,sizeof h);
for(int i=1;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
}
for(int i=1;i<=n1;i++)
{
memset(st,-1,sizeof st);
//每个男生对自己喜欢的女生（无论有没有男朋友）都试试
if(find(i))res++;
}
printf("%d\n",res);
return 0;
}