首页 > 代码库 > 51Nod 1212无向图最小生成树
51Nod 1212无向图最小生成树
prim
#include<stdio.h> #include<string.h> #define inf 0x3f3f3f3f int G[1001][1001]; int vis[1001],lowc[1001]; int prim(int G[][1001],int n){ int i,j,p,minc,res=0; memset(vis,0,sizeof(vis));//全部初值为0表示没有访问过; vis[1]=1; for(i=2;i<=n;i++) lowc[i]=G[1][i]; for(i=2;i<=n;i++){ minc=inf; p=-1; for(j=1;j<=n;j++){ if(vis[j]==0&&lowc[j]<minc) {minc=lowc[j];p=j;} } if(inf==minc) return -1;//原图不连通 res+=minc; vis[p]=1; for(j=1;j<=n;j++){//更新lowc[] if(vis[j]==0&&lowc[j]>G[p][j]) lowc[j]=G[p][j]; } } return res; } int main(){ int n,m; int x,y,w; while(~scanf("%d %d",&n,&m)){ memset(G,inf,sizeof(G)); while(m--){ scanf("%d%d%d",&x,&y,&w); G[x][y]=G[y][x]=w; } printf("%d\n",prim(G,n)); } }
Kruskal
#include<iostream> #include<cstring> #include<string> #include<cstdio> #include<algorithm> using namespace std; #define MAX 50005 int father[MAX], son[MAX]; int v, l; typedef struct Kruskal //存储边的信息 { int a; int b; int value; }; bool cmp(const Kruskal & a, const Kruskal & b) { return a.value < b.value; } int unionsearch(int x) //查找根结点+路径压缩 { return x == father[x] ? x : unionsearch(father[x]); } bool join(int x, int y) //合并 { int root1, root2; root1 = unionsearch(x); root2 = unionsearch(y); if(root1 == root2) //为环 return false; else if(son[root1] >= son[root2]) { father[root2] = root1; son[root1] += son[root2]; } else { father[root1] = root2; son[root2] += son[root1]; } return true; } int main() { int ncase, ltotal, sum, flag; Kruskal edge[MAX]; scanf("%d%d", &v, &l); ltotal = 0, sum = 0, flag = 0; for(int i = 1; i <= v; ++i) //初始化 { father[i] = i; son[i] = 1; } for(int i = 1; i <= l ; ++i) { scanf("%d%d%d", &edge[i].a, &edge[i].b, &edge[i].value); } sort(edge + 1, edge + 1 + l, cmp); //按权值由小到大排序 for(int i = 1; i <= l; ++i) { if(join(edge[i].a, edge[i].b)) { ltotal++; //边数加1 sum += edge[i].value; //记录权值之和 //cout<<edge[i].a<<"->"<<edge[i].b<<endl; } if(ltotal == v - 1) //最小生成树条件:边数=顶点数-1 { flag = 1; break; } } if(flag) printf("%d\n", sum); else printf("data error.\n"); return 0; }
51Nod 1212无向图最小生成树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。