首页 > 代码库 > [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]最小生成树模板