C++(g++ 7.5.0) 解法, 执行用时: 2ms, 内存消耗: 348K, 提交时间: 2023-02-07 09:50:59

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int mod=31011;
const int mac=1e3+10;

struct node
{
    int u,v,w;
    bool operator <(const node &a)const{
        return w<a.w;
    }
}eg[mac<<1];

int father[mac],l[mac],r[mac],c[mac],cnt,sum;

int find(int x){return x==father[x]?x:find(father[x]);}
//dfs(l[i],i,0)
void dfs(int now,int x,int num)
{
    if (now>r[x]){//从l[i]搜索到r[i]，判断第i个长度的边是否用了c[cnt]个
        sum+=(num==c[x]);
        return;
    }
    int fa=find(eg[now].u),fb=find(eg[now].v);
    if (fa!=fb){
        father[fa]=fb;
        dfs(now+1,x,num+1);
        father[fa]=fa;father[fb]=fb;
    }
    dfs(now+1,x,num);
}

int main()
{
    //freopen("in.txt","r",stdin);
    int n,m;
    scanf ("%d%d",&n,&m);
    for (int i=1; i<=m; i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        eg[i]=node{u,v,w};
    }
    sort(eg+1,eg+1+m);
    for (int i=1; i<=n; i++) father[i]=i;
    int tot=0;
    for (int i=1; i<=m; i++){
        if (eg[i].w!=eg[i-1].w) r[cnt]=i-1,l[++cnt]=i;
        int fa=find(eg[i].u),fb=find(eg[i].v);
        if (fa!=fb) ++c[cnt],father[fa]=fb,++tot;//c[cnt]用了第cnt边长度几次
    }
    r[cnt]=m;
    if (tot!=n-1) {printf("0\n");return 0;}
    for (int i=1; i<=n; i++) father[i]=i;
    int ans=1;
    for (int i=1; i<=cnt; i++){
        sum=0;
        dfs(l[i],i,0);
        ans=ans*sum%mod;
        for (int j=l[i]; j<=r[i]; j++){
            int fa=find(eg[j].u),fb=find(eg[j].v);
            if (fa!=fb) father[fa]=fb;
        }
    } 
    printf("%d\n",ans);
    return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 3ms, 内存消耗: 468K, 提交时间: 2022-07-28 19:52:49

#include<bits/stdc++.h>
using namespace std;
struct edge{
	int a,b,c;
}e[1001];
int n,f[101],l[1002],c[1001],cnt,tot;
bool cmp(const edge &x,const edge &y){
	return x.c < y.c;
}
void init(){
	for (int i = 1;i <= n;i++)
		f[i] = i;
}
int find(int x){
	while (f[x] != x)
		x = f[x];
	return x;
}
void dfs(int now,int s,const int &x){
	if (s == c[x]){
		tot++;
		return;
	}
	int a,b;
	for (;now < l[x + 1];now++){
		a = find(e[now].a);
		b = find(e[now].b);
		if (a != b){
			f[a] = b;
			dfs(now + 1,s + 1,x);
			f[a] = a;
		}
	}
}
int main(){
	int m,x,y,i,j;
	cin>>n>>m;
	for (i = 1;i <= m;i++)
		cin>>e[i].a>>e[i].b>>e[i].c;
	sort(e + 1,e + 1 + m,cmp);
	init();
	for (i = 1;i <= m;i++){
		if (e[i].c != e[i - 1].c)
			l[++cnt] = i;
		x = find(e[i].a);
		y = find(e[i].b);
		if (x != y){
			f[x] = y;
			tot++;
			c[cnt]++;
		}
	}
	if (tot != n - 1){
		cout<<0;
		return 0;
	}
	l[cnt + 1] = m + 1;
	int ans = 1;
	init();
	for (i = 1;i <= cnt;i++){
		if (!c[i])continue;
		tot = 0;
		dfs(l[i],0,i);
		ans = ans * tot % 31011;
		for (j = l[i];j < l[i + 1];j++)
			f[find(e[j].a)] = find(e[j].b);
	}
	cout<<ans;
	return 0;
}