目录
一、最小生成树
1.Prim算法
分为朴素Prim算法和堆优化Prim算法。写法和dijikstra算法类似，堆优化过程也类似，可类比学习。首先，介绍一下朴素Prim算法。
适用于稠密图。
#include<iostream>
#include<cstring>
using namespace std;
const int N=510,INF=0x3f3f3f3f;
int g[N][N];
int dist[N];//点到集合的距离
bool st[N];//标记集合中的点
int n,m;
void prim(){
memset(dist,0x3f,sizeof dist);
int res=0;
for(int i=0;i<n;i++){ //n次迭代
int t=-1;
for(int j=1;j<=n;j++){
if(!st[j]&&(t==-1||dist[t]>dist[j])){
t=j;//选择不在集合中且距离集合距离最短的点
}
}
if(i&&dist[t]==INF){//不是第一次迭代且距离集合最短为INF
puts("impossible");
return;
}
if(i) res+=dist[t];//1 加入权值
//用该点更新其他点到集合的距离
for(int j=1;j<=n;j++) dist[j]=min(dist[j],g[t][j]);//2 注意12先后，这一步可能会因为负环改变dist[t]
st[t]=true;
}
printf("%d",res);
}
int main(){
scanf("%d%d",&n,&m);
memset(g,0x3f,sizeof g);
while(m--){
int a,b,w;scanf("%d%d%d",&a,&b,&w);
g[a][b]=g[b][a]=min(g[a][b],w);
}
prim();
return 0;
}
堆优化Prim算法，适用于稀疏图。
由于稀疏图的求解也可用Kruskal算法，且堆优化实际几乎不常用，因此根据实用主义思想，这里不具体介绍堆优化Prim算法。
2.Kruskal算法
不需要邻接表、 邻接矩阵 来 存 图 ， 用 结构体 存 边 即可。 使用到了并查集的思想。
#include<iostream>
#include<algorithm>
using namespace std;
const int N=200010;
int n,m;
int p[N];
struct Edge{
int a,b,w;
bool operator< (const Edge &other) const{
return w<other.w;
}
}edges[N];
int find(int x){
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
int a,b,w;scanf("%d%d%d",&a,&b,&w);
edges[i]={a,b,w};
}
sort(edges,edges+m);
for(int i=1;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,w=edges[i].w;
a=find(a),b=find(b);
if(a!=b){//若不连通则可加
p[a]=b;
res+=w;
cnt++;
}
}
if(cnt<n-1) puts("impossible");
else printf("%d\n",res);
return 0;
}
二、二分图
1.判断二分图--染色体法
染色法的基本思想是尝试用两种颜色对图中的顶点进行染色，使得相邻顶点颜色不同。如果能够成功染色，则图是二分图；否则，图不是二分图。
#include<iostream>
#include<cstring>
using namespace std;
int n,m;
const int N=100010,M=200010;
int h[N],e[M],ne[M],idx;
int color[N];
void add(int a,int b){
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]){
if(!dfs(j,3-c)) return false;
}else if(color[j]==c) return false;//冲突
}
return true;
}
int main(){
scanf("%d%d",&n,&m);
memset(h,-1,sizeof h);
while(m--){
int a,b;scanf("%d%d",&a,&b);
add(a,b),add(b,a);
}
bool flag=true;
for(int i=1;i<=n;i++){
if(!color[i]){
if(!dfs(i,1)){
flag=false;
break;
}
}
}
if(flag) puts("Yes");
else puts("No");
return 0;
}
2.求二分图最大匹配--匈牙利算法
#include<iostream>
#include<cstring>
using namespace std;
const int N=510,M=10010;
int n1,n2,m;
int h[N],e[M],ne[M],idx;
int match[N]; //存右边点匹配的左边点
bool st[N]; //每次不能重复匹配的点
void add(int a,int b){
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
bool find(int x){
for(int i=h[x];i!=-1;i=ne[i]){//从它的备选中选择点进行匹配
int j=e[i];
if(!st[j]){ //该备选点未被匹配
st[j]=true;//先标记为不能被匹配
if(match[j]==0||find(match[j])){ //该点未被匹配||被匹配了但匹配它的点有其它选择
match[j]=x;
return true;
}
}
}
return false;
}
int main(){
scanf("%d%d%d",&n1,&n2,&m);
memset(h,-1,sizeof h);
while(m--){
int a,b;scanf("%d%d",&a,&b);
add(a,b);//从左部分找，只需连left->right
}
int res=0;
for(int i=1;i<=n1;i++){
memset(st,false,sizeof st);
if(find(i)) res++;
}
printf("%d\n",res);
return 0;
}
标签：二分,Prim,idx,int,Kruskal,算法,染色法,include From： https://blog.csdn.net/a2946501058/article/details/145166859