题目链接：POJ-1287
[kuangbin带你飞]专题六最小生成树
题目描述：
您被分配设计广泛区域中某些点之间的网络连接。您将获得该区域中的一组点，以及可连接成对点的电缆的一组可能路线。对于两点之间的每条可能路线，您将获得连接该路线上的点所需的电缆长度。请注意，在两个给定点之间可能存在许多可能的路径。假设给定的可能路线（直接或间接）连接该区域中的每两个点。
您的任务是为该区域设计网络，以便在每两个点之间存在连接（直接或间接）（即，所有点都是互连的，但不一定是通过直接电缆），并且总长度为用过的电缆很少。
思路
Prim算法：
Prim算法就是定义mat用来存图，dist数组用来存每个点到最小生成树的最短距离，vis数组标记此点是否已经在最小生成树中了（防止出现环）。
实际操作就是先随便把一个点加入到生成树里（一般是第一个点），然后寻找与该点距离最短的点并加入，然后在寻找与1,2点相连最短的点，并加入到生成树中，就这样不断的加下去，直到加入的点数与原图一致终止；
可以自己手动模仿一下过程，其实还是好理解的！
##易错点
1.每次加入前确保加入的权值比之前加入的权值要小，否则不加入；
如 第一次 给出 1-2边的权值为3， 然后某次加边操作说 1-2边权值为10， 这时候我们保留第一次的权值（保留权值较小的那次）
2.题意说是边可能无限，那么大概不能用Kruskal算法来做；Prim算法用来存顶点，而Kruskal算法用来存边，当边很多或者不确定是，我们可能无法用Kruskal算法来做（当然，现在2018年10月9日16:39:24可能还是不能做的，以后说不定也可以做）
代码:
Prim算法：
#include <iostream>
#include <string.h>
using namespace std;#define MAX 5050
#define INF 0x3f3f3f3fint mat[MAX][MAX], vis[MAX], dist[MAX];void init(int n)
{
for(int i = 1; i<=n; i++){
for(int j = 1; j<=n; j++){
mat[i][j] = INF;}dist[i] = INF;}
}void Union(int x, int y, int val)
{
if(val < mat[x][y]){
mat[x][y] = mat[y][x] = val;}
}int Prim(int n)
{
int sum = 0;dist[1] = 0;for(int i = 1; i<=n; i++){
int min_dist = INF, min_vertex;for(int j = 1; j<=n; j++){
if(!vis[j] && dist[j] < min_dist){
min_dist = dist[j];min_vertex = j;}}vis[min_vertex] = 1;sum += min_dist;for(int j = 1; j<=n; j++){
if(!vis[j] && mat[min_vertex][j] < dist[j]){
dist[j] = mat[min_vertex][j];}}}return sum;
}int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n, m;while(cin >> n, n != 0){
cin >> m;init(n);memset(vis, 0, sizeof(vis));for(int i = 0; i<m; i++){
int x, y, val;cin >> x >> y >> val;Union(x, y, val);}cout << Prim(n) << endl;}return 0;
}