NCSTOJ :1080 : [啊哈算法]镖局运镖（最小生成树）

镖局运镖（最小生成树）"/>

NCSTOJ :1080 : [啊哈算法]镖局运镖（最小生成树）

Description
最近小哼迷上了《龙门镖局》，从恰克图道武夷山，从张家口道老河口，从迪化道佛山，从蒙自道奉天…古代镖局的运镖，也就是现在的物流。镖局每到一个地方开展业务，都需要堆运镖途中的绿林好汉进行打点（不给钱就不让过路）。好说话的打点费就比较低，不好说话的打点费就比较高。城镇类似如下，顶点是城镇编号，边上的值表示这条道路上打点绿林好汉需要的银子数。

请你帮镖局算算，如果从1号城镇出发，遍历每个城镇最少需要准备多少打点银子？

Input
输入第一行包括两个正整数n,m。n代表城镇个数，m表示道路个数（1 < n,m < 100）。

后面的m行分别包含三个正整数a,b,c，表示在从城镇a 到 城镇b的道路上需要交纳的银子数。

Output
输出从1号城镇出发，遍历每个城镇最少需要准备的银子数。
Sample Input
6 9
2 4 11
3 5 13
4 6 3
5 6 4
2 3 6
4 5 7
1 2 1
3 4 9
1 3 2
Sample Output
19

#include<iostream>
#include<algorithm>using namespace std;
struct edge{int left;int right;int worth;//存储每一条道路的信息}e[105];//判断路径之间是否串联要用到并查集
int n,m;
int f[105];
bool fuction(struct edge e1,struct edge e2)
{return e1.worth<e2.worth;
}
void init(){for(int i=1;i<=n;i++)f[i]=i;//对并查集进行初始化
}int getf(int v)
{if(f[v]==v)return f[v];else{f[v]=getf(f[v]);return f[v];}//判断当前道路最终是与那一条路是想通的}bool merge(int v,int u)
{//对不同路径的合并	int i,j;i=getf(v);j=getf(u);if(i==j)return true;else {f[j]=i;return  false;}}int main(){cin>>n>>m;init();for(int i=1;i<=m;i++){int k1,k2,k3;  //输入路径的信息cin>>k1>>k2>>k3;e[i].left=k1;e[i].right=k2;e[i].worth=k3;}sort(e+1,e+m+1,fuction);//这里要注意由于并查集的影响该问题中的所有数//组都是从1开始的所以排序的时候要注意这一点int sum=0,count=0;for(int i=1;i<=m;i++){if(!merge(e[i].left,e[i].right))//因为是递增的路费的顺序{                              //所以只要两条路没有连通就将它们//合并并获得该条路的路费count++;sum+=e[i].worth;}if(count==n-1)break;}cout<<sum;return 0;}