题目描述

现在给出了一个简单无向加权图。

你不满足于求出这个图的最小生成树，而希望知道这个图中有多少个不同的最小生成树。

如果两颗最小生成树中至少有一条边不同，则这两个最小生成树就是不同的。

输入格式
第一行包含两个整数 n 和 m，表示该无向图的节点数和边数，节点用 1~n 编号。

接下来 m 行，每行包含三个整数 a,b,c，表示节点 a 和节点 b 之间存在一条边，权值为 c。

输出格式
输出不同的最小生成树有多少个。

你只需要输出数量对 31011 的模就可以了。

数据范围
1≤n≤100,
1≤m≤1000,
1≤c≤109,
数据保证不会出现自回边和重边。
具有相同权值的边不会超过 10 条。

样例

输入样例：
4 6
1 2 1
1 3 1
1 4 1
2 3 2
2 4 1
3 4 1
输出样例：
8

算法1

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int Max=1005;
const int mod=31011;
int n,m,size,s,tot=0,ans=1;
long long sum;
int fa[105];
struct edge{
    int x,y,len;
    friend bool operator < (edge a,edge b){return a.len < b.len;}
    } edges[Max];
struct tree{int l,r,num,id;} a[Max];

int find(int v){return fa[v]==v ?  v : find(fa[v]);}//注意，在有dfs回溯的时侯，不能采用压缩路径；    
void dfs(int i,int p,int num)
{
    if(p == a[i].r+1)
    {
      if(num == a[i].num) sum++;
      return;
    }
    int fax = find(edges[p].x),fay = find(edges[p].y);
//此处采用压缩路径会导致回溯的时候出现父节点指向错误比如fa[1]=4,fa[2]=4,然后此时要连接3,4那么fa[4]=fa[1]=fa[2]=3 ，而回溯撤边的时候，fa[1],fa[2]的父节点本应为4,但由于压缩路径其为3.    
    if(fax != fay)
    {
      fa[fay] = fax;
      dfs(i,p+1,num+1);
      fa[fay] = fay,fa[fax] = fax;
    }
    dfs(i,p+1,num);  //注意不能用else，因为这里的意思是不选择这条边，每条边都有这种情况。
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) fa[i] = i;
    for(int i=1;i<=m;i++) cin>>edges[i].x>>edges[i].y>>edges[i].len;
    sort(edges+1,edges+m+1);
    for(int i=1;i<=m;i++)
    {
      int x=find(edges[i].x),y=find(edges[i].y);
      if(edges[i].len != edges[i-1].len) a[++tot].l=i,a[tot-1].r=i-1;
      if(x != y)
      {
        s++;
        fa[y] = x;
        a[tot].num++;
      }
    }
    if(s != n-1) {putchar('0');return 0;}
    a[tot].r = m;
    for(int i=1;i<=n;i++) fa[i] = i;
    for(int i=1;i<=tot;i++)
    {
      sum=0;
      dfs(i,a[i].l,0);
      if(sum) ans=(long long)(ans * sum) % mod;
      for(int j=a[i].l;j<=a[i].r;j++)
      {
        int fax = find(edges[j].x),fay = find(edges[j].y);
           if(fax != fay) fa[fay] = fax;
      }
    }
    printf("%d\n",ans);
    return 0;
}