首页 > 代码库 > 最小生成书模板
最小生成书模板
http://acm.fjut.edu.cn/Problem.jsp?pid=1545
FJUTOJ 1545
Prim
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <iostream> 5 6 using namespace std; 7 #define M 105 8 9 const int INF=1<<29; 10 11 int n,m,arr[M][M]; 12 13 int prim() 14 { 15 int dis[M],vis[M],i,j,u,ans=0; 16 for(i=1;i<=n;i++) 17 dis[i]=arr[1][i],vis[i]=0; 18 vis[1]=1; 19 for(i=1;i<n;i++) 20 { 21 int mi=INF; 22 for(j=1;j<=n;j++) 23 { 24 if(!vis[j]&&dis[j]<mi) 25 { 26 mi=dis[j]; 27 u=j; 28 } 29 } 30 vis[u]=1; 31 ans+=dis[u]; 32 for(j=1;j<=n;j++) 33 { 34 if(!vis[j]&&arr[u][j]<dis[j]) 35 { 36 dis[j]=arr[u][j]; 37 } 38 } 39 } 40 return ans; 41 } 42 43 int main() 44 { 45 int i,j,a,b,c; 46 while(scanf("%d",&n)&&n) 47 { 48 for(i=1;i<=n;i++) 49 { 50 for(j=1;j<=n;j++) 51 { 52 arr[i][j]=INF; 53 } 54 } 55 scanf("%d",&m); 56 while(m--) 57 { 58 scanf("%d%d%d",&a,&b,&c); 59 arr[a][b]=arr[b][a]=min(arr[a][b],c); 60 } 61 printf("%d\n",prim()); 62 63 } 64 return 0; 65 }
kruskal
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 struct edge 5 { 6 int from,to,cost; 7 }arr[105*105]; 8 int n,m,pre[105]; 9 void init() 10 { 11 for(int i=1;i<=n;i++) 12 { 13 pre[i]=i; 14 } 15 } 16 int findx(int x) 17 { 18 if(pre[x]==x)return x; 19 else return pre[x]=findx(pre[x]); 20 } 21 void join(int x,int y) 22 { 23 int fx=findx(x),fy=findx(y); 24 if(fx==fy)return; 25 pre[fy]=fx; 26 } 27 bool same(int x,int y) 28 { 29 return findx(x)==findx(y); 30 } 31 bool cmp(edge a,edge b) 32 { 33 return a.cost<b.cost; 34 } 35 int kruskal() 36 { 37 int ans=0; 38 sort(arr+1,arr+1+m,cmp); 39 for(int i=1;i<=m;i++) 40 { 41 if(same(arr[i].from,arr[i].to)) 42 { 43 continue; 44 } 45 join(arr[i].from,arr[i].to); 46 ans+=arr[i].cost; 47 } 48 return ans; 49 } 50 int main() 51 { 52 while(scanf("%d",&n)&&n) 53 { 54 scanf("%d",&m); 55 init(); 56 for(int i=1;i<=m;i++) 57 { 58 scanf("%d%d%d",&arr[i].from,&arr[i].to,&arr[i].cost); 59 } 60 printf("%d\n",kruskal()); 61 } 62 }
最小生成书模板
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。