最小生成树模板

Kruskal算法模板

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; struct node{ int x,y;//树一条边的起点和终点； int w;// 边权（边的价值或大小） }a[110]; int pre[110];//每个点的信息； 并查集所用； bool cmp(struct node a,struct node b) { return a.w<b.w; } int find(int root)// 查找函数（并查集） { if(root!=pre[root]) root=find(pre[root]); return pre[root]; } int main() { int n,i,m; while(scanf("%d %d",&n,&m),n) { memset(pre,0,sizeof(pre)); int sum=0,num=0; for(i=1;i<=m;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w);//输入各个边的起点、终点和权值； sort(a+1,a+1+m,cmp);// 对各个边进行排序； for(i=1;i<=n;i++) pre[i]=i; for(i=1;i<=m;i++)// 从小到大开始枚举测试边；用并查集判断是否构成环； 不构成则加入； { int f1=find(a[i].x); int f2=find(a[i].y); if(f1!=f2) { pre[f1]=f2; sum+=a[i].w;//存储最小的边权和； num++; } if(num==n-1) break;// 满足树的性质； 边的条数==点的个数-1； } if(num==n-1)//判断是否存在； printf("%d\n",sum); else printf("?\n"); } return 0; }

Prim 模板

#include<iostream> #include<cstdio> #include<vector> #include<algorithm> #include<queue> #define ll long long using namespace std; struct node{ int to,len; node(int x,int y){to=x,len=y;} friend bool operator < (node a,node b){ return a.len>b.len; } }; int n,m; priority_queue<node>q; int ans=0; bool vis[1010]; vector<node>v[1010]; void link(int x,int y,int z){ v[x].push_back(node(y,z)); v[y].push_back(node(x,z)); } int main(){ scanf("%d%d",&n,&m); for(int i=0; i<m; i++){ int x,y,z; scanf("%d%d%d",&x,&y,&z); link(x,y,z); } vis[1]=true; for(int i=0; i<v[1].size(); i++)q.push(node(v[1][i].to,v[1][i].len)); int sum=1; while(!q.empty()){ node t=q.top(); q.pop(); if(vis[t.to])continue; sum++; ans+=t.len; vis[t.to]=true; if(sum==n)break; for(int i=0; i<v[t.to].size(); i++)if(!vis[v[t.to][i].to])q.push(node(v[t.to][i].to,v[t.to][i].len)); } if(sum==n)printf("%d\n",ans); else printf("-1\n"); return 0; }

模板二： 模板题

#include <iostream> #include<cstring> #include<cstdio> #include<cmath> #include<cstdlib> #define MAX 27 //图的规模 #define INF 99999999 //定义无穷大 using namespace std; int N; //节点的数目N //此外，在这里可能会有路径的数目M int map[MAX][MAX]; //邻接表 int micost[MAX]; //到上一个点的最小路径 int vis[MAX]; //记录该点有没有加入最小生成树中 void Prim() { int i,j,v,Min; int ans; //最小生成树的总权值 //1是第一个加入该最小生成树的节点 for(i=1;i<=N;i++) { micost[i]=map[1][i]; vis[i]=0; }//初始化节点 //定义每个节点的micost为1到其他点的距离 micost[1]=0; vis[1]=1; //起点的上一个节点没有节点，所以为0 //定义起点已经加入了最小生成树 ans=0; //初始化最小生成树的权值为零 //注意在循环里起点不包含进去 //为了防止错误 //因为不包含起点所以循环要从i=2开始 for(i=2;i<=N;i++) { Min=INF; for(j=2;j<=N;j++) { if(!vis[j]&&Min>micost[j]) v=j,Min=micost[j]; }//找micost最小的节点并加入最小生成树 vis[v]=1; if(Min!=INF) ans=ans+Min; for(j=2;j<=N;j++) { if(!vis[j]&&micost[j]>map[v][j]) micost[j]=map[v][j]; }//更新节点 } cout<<ans<<endl; } int main() { int i,j,num,x,y,z; char a,b; while(cin>>N,N)//输入图的节点数，路径数，（一般情况下） { for(i=1;i<=N;i++) for(j=1;j<=N;j++) { if(i==j)map[i][j]=0; else map[i][j]=INF; }//初始化邻接表 for(i=1;i<N;i++) { cin>>a>>num; for(j=1;j<=num;j++){ cin>>b>>z; x=a-64; y=b-64; map[x][y]=map[y][x]=z; } }//输入图 Prim(); } return 0; }