Problem Description在图论中，树：任意两个顶点间有且只有一条路径的图。
生成树：包含了图中所有顶点的一种树。
最小生成树：对于连通的带权图(连通网)G，其生成树也是带权的。生成树T各边的权值总和称为该树的权，权最小的生成树称为G的最小生成树(Minimum Spanning Tree)。最小生成树可简记为MST。
但是，对于一个图而言，最小生成树并不是唯一的。
现在,给你一个连通的有权无向图，图中不包含有自环和重边，你的任务就是寻找出有多少条边，它至少在一个最小生成树里。图保证连通。
Input输入数据第一行包含一个整数T，表示测试数据的组数。对于每组测试数据：
第一行包含两个整数n,m(1<n<100000,n-1<m<100000)，接下来m行，每行三个整数a,b,v(1<=a,b<=n,1<v<500)，表示第i条路线连接景点A和景点B，距离是V。两个数字之间用空格隔开。
Output Sample Input Sample Output Source
1 #include "bits/stdc++.h" 2 #define mem(a,b) memset(a,b,sizeof(a)) 3 using namespace std; 4 typedef long long LL; 5 const int MAX=100005; 6 int n,m,T,ans; 7 int fa[MAX]; 8 struct Edge{ 9 int u,v,w; 10 bool operator <(const Edge &cc) const { 11 return w<cc.w; 12 } 13 }edge[MAX]; 14 void init(){ 15 int i,j; 16 scanf("%d%d",&n,&m); 17 for (i=1;i<=m;i++){ 18 scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w); 19 } 20 sort(edge+1,edge+m+1); 21 for (i=1;i<=n;i++) 22 fa[i]=i; 23 ans=0; 24 } 25 int getfather(int x){ 26 if (fa[x]==x) return x; 27 else return fa[x]=getfather(fa[x]); 28 } 29 int main(){ 30 freopen ("tree.in","r",stdin); 31 freopen ("tree.out","w",stdout); 32 int i,j,cas(0); 33 scanf("%d",&T); 34 while (T--){ 35 init(); 36 for (i=1;i<=m;i=j){ 37 for (j=i;edge[j].w==edge[i].w;j++){ 38 if (getfather(edge[j].v)!=getfather(edge[j].u)) 39 ans++; 40 } 41 for (j=i;edge[j].w==edge[i].w;j++){ 42 int tx=getfather(edge[j].u); 43 int ty=getfather(edge[j].v); 44 if (tx!=ty) 45 fa[tx]=ty; 46 } 47 } 48 printf("%d\n",ans); 49 } 50 return 0; 51 }
原文：http://www.cnblogs.com/keximeiruguo/p/6055897.html
