【题目链接】:http://www.lydsy.com/JudgeOnline/problem.php?id=1016

【题意】

【题解】

/*

    两个最小生成树T和T';

    它们各个边权的边的数目肯定是一样的;

    且相同边权的边;

    那些边所形成的联通性是一样的;

    可以考虑T和T'的形成;

    比如说一开始

    T和T'都是空的;

    然后把边按边权从小到大排序后

    找到的第一种边权的边权为

    v1

    且bian[left..right]都是这种边权的边;

    然后假设T是我们正常用卡鲁斯卡尔算法搞出来的最小生成树;

    那么T在这个阶段肯定会在这right-left+1条边中选择x条边;

    那么这个时候我们再想想T'要怎么选?

    假设我们选y条边

    这里我们分类讨论一下

        假如y>x，

            这种情况是不可能的;

            因为如果y可以大于x;

            那就说明T还可以再加一条边权最小的边v1联通更多的分量;

            而我们在做克鲁斯卡尔的时候已经保证了不能添加更多的分量;

            所以可以排除;

       假如y<x

            这种情况也是不可能的;

            假设我们少选了一条边

            那么这条边链接的两个分量必然是要用更大的边权来链接;

            这就不符合最小生成树了;

            所也可以排除;

      综上可知

      x==y;

      这里所选的y条边的各个节点的连通性必然和x条边的联通性一样;

      因为如果不一样的话,

      那么哪里不一样呢??

        ->假设在T'中相对于T有两个分量没有连通在一起,那么你可以选择T中连接这两个分量的

            边啊。而且因为是升序排的,所以肯定连了更优啊;

          但是显然不可能再有这样的连法了,因为T是正确的最小生成树;

          你如果能找到这样的连法的话,就说明T是不正确的了;

          这就矛盾了;

   根据上面的推导可知;

   每个最小生成树;

   出现的不同边权的种类是一样的,且各种边权的数目是确定的;

   而且只要边权的数目确定了,这个边权造成的连通性的变化都是一样的;

   所以我们只要枚举对于每一种边权,可以用哪些连着不同节点的边,但边权和它相同的边交换一下

   一开始做的最小生成树的边就好了;

   比如第i种边权的边v[i],出现的次数为numv[i];

   然后在用克鲁斯卡尔算法算出的最小生成树中v[i]出现的次数为k;

   则从这numv[i]条边中选出k条边来,看看是不是这k条边中每条边都能对联通量贡献;(如果有一条边在做

   的过程中边的两段链接的联通量已经是在一起的了,就退出,表示不行);

   因为要回溯,所以这里的并查集不能加状态压缩。

   当然n也不大就是了;

    因为有说同边权的边的数目不超过10,所以2^10是可以接受的.

    搜一波;

    然后用乘法原理乘起来就好;

*/

【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define rei(x) scanf("%d",&x)

#define rel(x) scanf("%lld",&x)

typedef pair<int, int> pii;

typedef pair<LL, LL> pll;

const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 };

const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 };

const double pi = acos(-1.0);

const int M = 1100;

const int N = 110;

const int MOD = 31011;

struct abc

{

    int x, y,z;

};

int n, m,f[N],tot = 0,tot1 = 0,num[M],sum = 0,ans = 1;

abc bian[M];

bool cmp1(abc a, abc b)

{

    return a.z < b.z;

}

int ff(int x)

{

    if (f[x] == x) return x;

    else

        return ff(f[x]);

}

void dfs(int l, int r, int now)

{

    if (now == num[tot])

    {

        sum++;

        return;

    }

    if (l > r) return;

    int x = bian[l].x, y = bian[l].y;

    int r1 = ff(x), r2 = ff(y);

    //这里f[r1]==r1,f[r2]==r2;

    if (r1 != r2)

    {

        f[r1] = r2;

        dfs(l + 1, r, now + 1);

        f[r1] = r1, f[r2] = r2;

    }

    dfs(l + 1, r, now);

}

int main()

{

    //freopen("F:\\rush.txt", "r", stdin);

    rei(n), rei(m);

    rep1(i, 1, m)

        rei(bian[i].x), rei(bian[i].y), rei(bian[i].z);

    sort(bian + 1, bian + 1 + m,cmp1);

    rep1(i, 1, n)

        f[i] = i;

    rep1(i, 1, m)

    {

        int l = i, r = i;

        while (r + 1 <= m && bian[r + 1].z == bian[l].z) r++;

        tot1++;

        rep1(j, l, r)

        {

            int x = bian[j].x, y = bian[j].y;

            int r1 = ff(x), r2 = ff(y);

            if (r1 != r2)

            {

                f[r1] = r2;

                tot++;

                num[tot1]++;

            }

        }

        i = r;

    }

    if (tot != n - 1)

        return puts("0"), 0;

    rep1(i, 1, n)

        f[i] = i;

    tot = 0;

    rep1(i, 1, m)

    {

        int l = i, r = i;

        while (r + 1 <= m && bian[r + 1].z == bian[l].z) r++;

        tot++;

        if (num[tot] == 0)

        {

            i = r;//。。。。。。bug点

            continue;

        }

        sum = 0;

        dfs(l, r, 0);

        ans = (ans*sum) % MOD;

        rep1(j, l, r)

        {

            int r1 = ff(bian[j].x), r2 = ff(bian[j].y);

            if (r1 != r2)

                f[r1] = r2;

        }

        i = r;

    }

    printf("%d\n", ans);

    return 0;

}