懒得讲了
#include <cstring>
#include <set>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 100010;
const int mod = 1000000007;
struct edge
{
int u, v, w;
}a[maxn];
int n, m;
int f[maxn];
int find(int x)
{
if(x != f[x])
return f[x] = find(f[x]);
return f[x];
}
bool cmp(edge a, edge b)
{
return a.w < b.w;
}
int main()
{
__int64 sum = 0;//最小生成树
__int64 cnt = 1;
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i++)
f[i] = i;
for(int i = 0 ; i < m; i++)
scanf("%d %d %d", &a[i].u, &a[i].v, &a[i].w);
sort(a, a+m, cmp);
int i = 0, j = 1;
for(i = 0; i < m;)
{
set < pair <int, int> > s;
int ss = 0;
for(j = i; j < m; j++)
{
if(a[j].w != a[i].w)
break;
int x = find(a[j].u);
int y = find(a[j].v);
if(x > y)
swap(x, y);
if(x != y)
{
//printf("%d %d\n", x, y);
s.insert(make_pair(x, y));
ss++;
}
}
int num = 0; //这一段可以用掉几条边
// 这里就是基本的最小生成树 一段一段处理每一段都是权值相等的边
//可能会想选不同的边导致连通性不同 这里有证明 连通性不会不同的
//用乘法原理 把每一段的可能的情况相乘就行了
for(; i < j; i++)
{
int x = find(a[i].u);
int y = find(a[i].v);
if(x != y)
{
f[y] = x;
num++;
}
}
sum += (__int64)num*a[i-1].w;
//printf("%d\n", s.size());
//分类讨论 ss是 一段里面 每条边的2个点所在的连通分量不同 但是有重复 s.size() 就是不同的数量 num是实际上用到的边数
if(num == 1)//实际上用了1条边
{
if(ss == 3)//可以用3条 但是用了1条 3种情况
cnt = (cnt*3)%mod;
else if(ss == 2)//可以用2条 但是用了1条 2种情况
cnt = (cnt*2)%mod;
}
else if(num == 2)//实际上用了2条边
{
if(s.size() == 3 && ss == 3)//有3条不重复的 但是用了2条 3种情况
cnt = (cnt*3)%mod;
else if(s.size() == 2 && ss == 3)//总共3条 有2条是不重复的 算一条不重复的和一条重复的 2种情况
cnt = (cnt*2)%mod;
}
else if(num == 3)//题目说权值一样的边最多3条 全部用上 这种情况是唯一的
{
cnt = cnt;
}
}
printf("%I64d %I64d\n", sum, cnt);
return 0;
}
TOJ 3886 Simplifying the Farm / 最小生成树+计数,布布扣,bubuko.com
TOJ 3886 Simplifying the Farm / 最小生成树+计数
原文：http://blog.csdn.net/u011686226/article/details/21889121