一、最小生成树算法
二、prim算法求最小生成树
prim和dijkstra算法类似，都是找到符合某种条件的点，然后更新。prim使用到已经构成的部分最小树所有结点中最小的距离。dijkstra算法是使用到起点最小的距离。
#include<bits/stdc++.h>
//858 prim最小生成树 （稠密图做法）
using namespace std;
const int N=210,INF=0x3f3f3f3f;
int n,m;
int g[N][N];
int dist[N];
bool st[N];
int prim()
{
int res=0;
for(int i=0;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找到的最短边仍然是INF，但是在第一次的时候所有的都是INF
if(i&&dist[t]==INF)return INF;
st[t]=true;
//由于存在负权自环所以在更新与点相连的所有边之前就保存边
if(i) res+=dist[t];
//展示了与dijkstra算法的不同之处，dist保存的是边，而不是某种路
for(int j=1;j<=n;j++)dist[j]=min(dist[j],g[t][j]);
}
return res;
}
int main()
{
cin>>n>>m;
memset(g,0x3f,sizeof g);
memset(dist,0x3f, sizeof dist);
for(int i=0;i<m;i++)
{
int a,b,c;
cin>>a>>b>>c;
g[a][b]=min(g[a][b],c);
}
int ans=prim();
if(ans==INF)puts("impossible");
else cout<<ans<<endl;
}
三、kruskal算法
思路简单：
#include<bits/stdc++.h>
//858 prim最小生成树 （稠密图做法）
using namespace std;
const int N=210,INF=0x3f3f3f3f;
int n,m;
int g[N][N];
int dist[N];
bool st[N];
int p[N];
struct Edge
{
int a,b,w;
bool operator <(const Edge &W)const
{
return w<W.w;
}
}edges[N];
int find(int a)
{
if(p[a]==a)return a;
else p[a]=find(p[a]); return p[a];
}
int main()
{
cin>>n>>m;
for(int i=0;i<m;i++)
{
int a,b,c;
cin>>a>>b>>c;
edges[i]={a,b,c};
}
sort(edges,edges+m);
for(int i=0;i<=n;i++)p[i]=i;
int res=0,cnt=0;
//遍历所有边
for(int i=0;i<m;i++)
{
//访问的顺序是有序的，只要连接的两个点没有在一个连通块里面
int a=edges[i].a,b=edges[i].b,c=edges[i].w;
a=find(a),b==find(b);
if(a!=b)
{
p[a]=b;//将其连接
res+=c;
cnt++;
}
}
if(cnt!=n-1)puts("impossible");
else cout<<res<<endl;
}
四、二分图（染色法判断是否有奇数环）
一个图是二分图当且仅当图中不含有奇数环（环中边的数量是奇数）
如果图当中不含有奇数环染色过程中没有矛盾。
思路：因为有多个连通块，而每次dfs就把连通块里面的所有的点全部遍历了，然后找其他连通块里面的点。
染色法dfs判断奇数环：对于当前点连接的所有边，判断这个点是否已经被染色，没有被染色继续染色，染色了，如果和相连的点的颜色相同，说明有奇数环。
#include<bits/stdc++.h>
//858 prim最小生成树 （稠密图做法）
using namespace std;
const int N=100010,M=200010;
int m,n;
int color[N];//染色情况
int e[N],ne[N],h[N],idx;
void add(int a,int b)
{
//e保存边idx的终点是什么
//ne保存idx这条边连接的下一条边
//更新h的值
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
//对一个连通块进行深度优先遍历
bool dfs(int u,int c)
{
color[u]=c;
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(!color[j])
{
//只要有一个不通就返回false
if(!dfs(j,3-c))return false;
}
else if(color[j]==c)return false;
}
return true;
}
int main()
{
//cmemset(color,0,sizeof color);
memset(h,-1,sizeof h);
cin>>n>>m;
for(int i=0;i<m;i++)
{
int a,b,c;
cin>>a>>b;
add(a,b),add(b,a);
}
int flag=0;
//遍历所有还没有遍历到的连通块，
for(int i=1;i<=n;i++)
{
if(!color[i])
{
if(!dfs(i,1))//随便取一个颜色，因为相邻两次循环就
{
flag=1;
break;
}
}
}
if(flag) puts("No");
else puts("Yes");
}
五、匈牙利算法（两组结点最多的匹配）
首先按照第一选择进行匹配，后面匹配冲突的时候，去看先匹配的那个可不可以调整。
使用bool数组st保证回去调整的时候不会选到同一个点，也就是一个点不会被同一个点匹配到两次。
#include<bits/stdc++.h>
//861二分图的最大匹配(匈牙利算法)
using namespace std;
const int N=500,M=100010;
int e[N],ne[M],h[N],idx;
int st[N];
int match[N],n1,n2,m;
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int find(int u)
{
for(int i=h[u];i!=-1;i=ne[i])//与u相连的所有点
{
int j=e[i];
//因为可能在调整的过程中重复调用find函数，此时st[j]已经为true
//不会再选这个点了
if(!st[j])//之前有没有被考虑过
{
st[j]=true;
//如果与其相连的点没有匹配
//或者匹配了但是可以更换
if(match[j]==0||find(match[j]))
{
//匹配上一个点
match[j]=u;
return true;
}
}
}
//尝试了所有的出边所连的点都不行的时候
return false;
}
int main()
{
cin>>n1>>n2>>m;
while(m--)
{
int a,b;
cin>>a>>b;
add(a,b);
}
int res=0;
for(int i=1;i<=n1;i++)
{
if(find(1))res++;
}
cout<<res<<endl;
}
