生活随笔
收集整理的这篇文章主要介绍了
08-图7 公路村村通 (30分)
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
是关于最小生成树的问题(包含v个顶点v-1条边，且边的权重和最小)，利用Kruskal贪心算法–将边合并成树，每次都取权值最小的边并且不构成回路，就利用到了并查集的算法（用数组存父节点）。
08-图7 公路村村通 (30分)
现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。
输入格式:
输入数据包括城镇数目正整数N（≤1000）和候选道路数目M（≤3N）；随后的M行对应M条道路，每行给出3个正整数，分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见，城镇从1到N编号。
输出格式:
输出村村通需要的最低成本。如果输入数据不足以保证畅通，则输出−1，表示需要建设更多公路。
#include
<stdio
.h
>
#define Max
1000
typedef struct
{int x
,y
;int cost
;
}box
;
typedef struct
{box data
[3005];int size
;
}heap
;
heap minh
;
int n
,m
;
int path
[1005];
void init(heap
&h
){h
.size
=0;h
.data
[0].cost
=-1;
}
void insert(heap
&h
,box a
){int i
=++h
.size
;for(;i
>0&&a
.cost
<h
.data
[i
/2].cost
;i
/=2){h
.data
[i
]=h
.data
[i
/2];}h
.data
[i
]=a
;
}
bool
judgeroot(box a
){while(path
[a
.x
]!=0) a
.x
=path
[a
.x
];while(path
[a
.y
]!=0) a
.y
=path
[a
.y
];if(a
.x
==a
.y
) return false;else {path
[a
.x
]=a
.y
;return true;}
}
box
del(heap
&h
){box min
=h
.data
[1];box last
=h
.data
[h
.size
--];if(h
.size
==0) return min
;int i
=2;for(;i
<=h
.size
;){if(h
.data
[i
].cost
>h
.data
[i
+1].cost
&&i
<h
.size
) i
++;if(h
.data
[i
].cost
<last
.cost
) {h
.data
[i
/2]=h
.data
[i
];i
*=2;}else break;}h
.data
[i
/2]=last
;return min
;
}
void swap(int
& a
,int
&b
){int temp
=a
;a
=b
;b
=temp
;
}
void Kruskal(){int v
=0,mincost
=0;while(v
!=n
-1&&minh
.size
!=0){box a
=del(minh
);if(judgeroot(a
)){v
++;mincost
+=a
.cost
;}} if(v
!=n
-1) printf("-1\n");else printf("%d\n",mincost
);
}
int
main(){box a
;scanf("%d%d",&n
,&m
);for(int i
=0;i
<m
;i
++){scanf("%d%d%d",&a
.x
,&a
.y
,&a
.cost
);insert(minh
,a
);}
Kruskal();
}
总结
以上是生活随笔为你收集整理的08-图7 公路村村通 (30分)的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
