首页 > 代码库 > [51nod1212]最小生成树模板
[51nod1212]最小生成树模板
解题关键:注意下标
解法一:prim算法
1 #include<bits/stdc++.h> 2 #define maxv 1002 3 #define maxm 50002 4 #define INF 0x3f3f3f3f 5 using namespace std; 6 typedef long long ll; 7 int cost[maxv][maxv]; 8 int mincost[maxv]; 9 bool used[maxv];10 int V;11 12 int prim(){13 fill(mincost,mincost+V,INF);14 mincost[0]=0;15 int res=0;16 17 while(true){18 int v=-1;19 for(int u=0;u<V;u++){20 if(!used[u]&&(v==-1||mincost[u]<mincost[v])) v=u;21 }22 if(v==-1) break;23 used[v]=true;24 res+=mincost[v];25 for(int u=0;u<V;u++){26 mincost[u]=min(mincost[u],cost[v][u]);27 }28 }29 return res;30 }31 int main(){32 for(int i=0;i<maxv;i++){33 for(int j=0;j<maxv;j++){34 cost[i][j]=INF;35 }36 }37 int n,m,t1,t2,t3;38 cin>>n>>m;39 V=n;40 for(int i=0;i<m;i++){41 cin>>t1>>t2>>t3;42 cost[t1-1][t2-1]=cost[t2-1][t1-1]=t3;43 }44 int ans=prim();45 cout<<ans<<endl;46 }
[51nod1212]最小生成树模板
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。