首页 > 代码库 > LA 6437 Power Plant (prim最小生成树)
LA 6437 Power Plant (prim最小生成树)
还是裸的最小生成树
#include<bits/stdc++.h> using namespace std; int T,N,M,P,K,a,b,c; int dist[1020],m[1020][1020]; bool p[1020]; void prim() { for(int i=1;i<=N;i++) { if(!p[i]) { int Min=1000020; for(int j=1;j<=N;j++) { if(p[j]&&m[i][j]!=0&&m[i][j]<Min) Min=m[i][j]; } dist[i]=Min; } } for(int i=1;i<=N-K;i++) { int Min=INT_MAX,k=0; for(int j=1;j<=N;j++) { if(!p[j]&&dist[j]<Min) { Min=dist[j]; k=j; } } if(k==0) return; p[k]=true; for(int j=1;j<=N;j++) { if(!p[j]&&m[k][j]!=0&&dist[j]>m[k][j]) dist[j]=m[k][j]; } } } int main() { scanf("%d",&T); for(int kase=1;kase<=T;kase++) { memset(p,false,sizeof(p)); memset(m,0,sizeof(m)); scanf("%d%d%d",&N,&M,&K); for(int i=1;i<=K;i++) { scanf("%d",&P); dist[P]=0; p[P]=true; } for(int i=1;i<=M;i++) { scanf("%d%d%d",&a,&b,&c); m[a][b]=c; m[b][a]=c; } prim(); int ans=0; for(int i=1;i<=N;i++) ans+=dist[i]; printf("Case #%d: %d\n",kase,ans); } return 0; }
LA 6437 Power Plant (prim最小生成树)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。