https://www.lydsy.com/JudgeOnline/problem.php?id=1016
无外乎两种：K算法和P算法（当然还有第三种但是我不会（滑稽）
P算法没法解于是用K算法。
发现K算法的正确性后其实我们需要做的工作就是从K算法找到一些边，可以用另一些边权一样的边替换并且是一棵生成树即可。
于是我们枚举即可。
（当然你会有两个问题：1.为什么边权一样即可替换，2.前面的边的操作对后面边是否有影响？）
（所以暴力选手不过脑子的话就很轻松的敲完代码走人了（比如我））
（实际为两个定理，分别为：
1.不同的最小生成树中,每种权值的边出现的个数是确定的。
2.不同的生成树中,某一种权值的边连接完成后,形成的联通块状态是一样的 。
百度一下。）
（https://blog.csdn.net/jarily/article/details/8902402可能这个解释靠谱些？）
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cctype>
#include<cstdio>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=;
const int M=;
const int p=;
inline int read(){
int X=,w=;char ch=;
while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();
return w?-X:X;
}
struct node{
int u,v,w;
}e[M];
struct range{
int l,r;
}a[M];
int fa[N],t[M],n,m,k,sum;
inline bool cmp(node a,node b){
return a.w<b.w;
}
int find(int x){
if(fa[x]==x)return x;
return find(fa[x]);
}
inline void unionn(int x,int y){
fa[x]=y;
}
inline void destory(int x,int y){
fa[x]=x;fa[y]=y;
}
void dfs(int l,int r,int d,int w){
if(l>r){
if(d==t[w])sum=(sum+)%p;
return;
}
if(r-l++d<t[w])return;
int u=find(e[l].u),v=find(e[l].v);
if(u!=v&&d<t[w]){
unionn(u,v);
dfs(l+,r,d+,w);
destory(u,v);
}
dfs(l+,r,d,w);
}
int main(){
n=read(),m=read();
for(int i=;i<=m;i++){
e[i].u=read(),e[i].v=read(),e[i].w=read();
}
sort(e+,e+m+,cmp);
for(int i=;i<=n;i++)fa[i]=i;
int cnt=;
for(int i=;i<=m;i++){
if(e[i].w!=e[i-].w){
a[++k].l=i;a[k-].r=i-;
}
int u=e[i].u,v=e[i].v;
u=find(u),v=find(v);
if(u!=v)t[k]++,cnt++,unionn(u,v);
}
a[k].r=m;
if(cnt!=n-){
puts("");return ;
}
int ans=;
for(int i=;i<=n;i++)fa[i]=i;
for(int i=;i<=k;i++){
if(!t[i])continue;
sum=;
dfs(a[i].l,a[i].r,,i);
ans=(ll)ans*sum%p;
for(int j=a[i].l;j<=a[i].r;j++){
int u=e[j].u,v=e[j].v;
u=find(u),v=find(v);
if(u!=v)unionn(u,v);
}
}
printf("%d\n",ans);
return ;
}
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/ +
+++++++++++++++++++++++++++++++++++++++++++