- #include<stdio.h>
- #include<string.h>
- #define MAXN 1001
- #define INF 0x3fffffff
- int n,m,g[MAXN][MAXN],vis[MAXN],dist[MAXN];
- void read();
- int prim();
- int main(){
- read();
- int cost = prim();
- printf("%d\n",cost);
- return 0;
- }
- void read(){
- scanf("%d %d",&n,&m);
- int i,j,v1,v2,cost1;
- for(i=1;i<=n;i++)
- for(j=1;j<=n;j++)
- g[i][j] = INF;
- for(i=1;i<=m;i++){
- scanf("%d %d %d",&v1,&v2,&cost1);
- g[v1][v2] = cost1;
- g[v2][v1] = cost1;
- }
- }
- int prim(){
- int cost,i,j;
- for(i=1;i<=n;i++){
- dist[i] = INF;
- vis[i] = 0;
- }
- dist[1] = 0;
- vis[1] = 1;
- for(i=1;i<=n;i++)
- if(g[1][i]!=INF&&i!=1)
- dist[i] = g[1][i];
- cost = 0;
- while(1){
- int mdist=INF,mindex=-1;
- for(i=1;i<=n;i++){
- if(mdist>dist[i] && vis[i]==0){
- mdist = dist[i];
- mindex = i;
- }
- }
- if(mindex==-1) break;
- cost += mdist;
- vis[mindex] = 1;
- for(i=1;i<=n;i++){
- if(g[mindex][i]!=INF && i!=mindex && vis[i]==0){
- if(dist[i]>g[mindex][i]) dist[i] = g[mindex][i];
- }
- }
- }
- int vsum=0;
- for(i=1;i<=n;i++) vsum += vis[i];
- if (vsum==n) return cost;
- else return -1;
- }
- View Code
来源: http://www.bubuko.com/infodetail-3493549.html